enter search term and/or author name
Price-based protocols for fair resource allocation: Convergence time analysis and extension to leontief utilities
Ashish Goel, Hamid Nazerzadeh
Article No.: 5
We analyze several distributed, continuous time protocols for a fair allocation of bandwidths to flows in a network (or resources to agents). Our protocols converge to an allocation that is a logarithmic approximation, simultaneously, to all...
Socially desirable approximations for dodgson’s voting rule
Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia
Article No.: 6
In 1876, Charles Lutwidge Dodgson suggested the intriguing voting rule that today bears his name. Although Dodgson’s rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point...
In this article, we study revenue maximizing envy-free pricing in multi-item markets: There are m indivisible items with unit supply each and n potential buyers where each buyer is interested in acquiring one item. The goal is to...
We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic...
Race to idle: New algorithms for speed scaling with a sleep state
Susanne Albers, Antonios Antoniadis
Article No.: 9
We study an energy conservation problem where a variable-speed processor is equipped with a sleep state. Executing jobs at high speeds and then setting the processor asleep is an approach that can lead to further energy savings compared to...