Problem: Resource hog

Cosmin Negruseri
08 ianuarie 2016

During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices' by George Varghese. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

IDENTIFYING A RESOURCE HOG

A software or hardware module needs to keep track of resources required by various users. The module needs a cheap way to find the user consuming the most resources. Since ordinary heaps are too slow, the device designers are willing to relax the system requirements to be off by a factor of 2. Can this relaxation in accuracy requirements be translated into a more efficient algorithm?

To paraphrase, the problem asks for a data structure with the following operations

• use_resources(name, quantity) which does resources[name] += quantity (quantity can also be negative)
• get_approximate_max() which returns name1 such that max(resources[name]) / 2 <= resources[name1] <= max(resources[name])

Using a map in combination with heap gives us a solution with O(log n) time for each of the two operations. Can we do better?