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
• 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.