ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 10 Issue 2, February 2014

Price-based protocols for fair resource allocation: Convergence time analysis and extension to leontief utilities
Ashish Goel, Hamid Nazerzadeh
Article No.: 5
DOI: 10.1145/2556949

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
DOI: 10.1145/2556950

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

Envy-free pricing in multi-item markets
Ning Chen, Xiaotie Deng
Article No.: 7
DOI: 10.1145/2567923

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

Dynamic programming for graphs on surfaces
Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos
Article No.: 8
DOI: 10.1145/2556952

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
DOI: 10.1145/2556953

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