Resource hog

Cosmin Negruseri
08 ianuarie 2016

During this winter break I was trying to improve my networking background. So I've spend some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices by George Varghese'. Thanks Vlad Balan for trecommending the book, it's fun to see how networking interacts heavily with the algorithms world. I read 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 author the problem asks for a datastructure with the following operations:
* use_resources(name, quantity) which does resources[name] += quantity
* get_approximate_top() which returns name1 such that max(resources[name]) / 2 <= resources[name1] <= max(resources[name])
Using a map in combination with a hash table gets a solution that has O(log n) complexity for use_resources and get_approximate
_top which is too slow.