Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 3 Issue 4, November 2007

Introduction to SODA 2002 and 2003 special issue
H. N. Gabow, Martin Farach-Colton, Michael A. Bender
Article No.: 36
DOI: 10.1145/1290672.1290673

Skip graphs
Gauri Shah, James Aspnes
Article No.: 37
DOI: 10.1145/1290672.1290674

Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for...

Optimal parallel selection
Yijie Han
Article No.: 38
DOI: 10.1145/1290672.1290675

We present an optimal parallel selection algorithm on the EREW PRAM. This algorithm runs in O(log n) time with n/log n processors. This complexity matches the known lower bound for parallel selection on the EREW PRAM...

Minimizing weighted flow time
Nikhil Bansal, Kedar Dhamdhere
Article No.: 39
DOI: 10.1145/1290672.1290676

We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O(k)-competitive for k weight classes. This implies an O(log...

The k-traveling repairmen problem
Satish Rao, Chris Harrelson, Jittat Fakcharoenphol
Article No.: 40
DOI: 10.1145/1290672.1290677

We consider the k-traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 8.497α-approximation algorithm for this generalization, where α denotes the best...

Algorithms for power savings
Rajesh Gupta, Sandeep Shukla, Sandy Irani
Article No.: 41
DOI: 10.1145/1290672.1290678

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the...

Guessing secrets efficiently via list decoding
Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
Article No.: 42
DOI: 10.1145/1290672.1290679

We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of N possible secrets. The player is asked...

Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets
Srinivasa Rao Satti, Venkatesh Raman, Rajeev Raman
Article No.: 43
DOI: 10.1145/1290672.1290680

We consider the indexable dictionary problem, which consists of storing a set S ⊆ {0,…,m − 1} for some integer m while supporting the operations of rank(x), which returns the number of...

Partial fillup and search time in LC tries
Wojciech Szpankowski, Svante Janson
Article No.: 44
DOI: 10.1145/1290672.1290681

Andersson and Nilsson introduced in 1993 a level-compressed trie (for short, LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent experimental results indicated a...

Finding the k shortest simple paths: A new algorithm and its implementation
John Hershberger, Matthew Maxel, Subhash Suri
Article No.: 45
DOI: 10.1145/1290672.1290682

We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed by Hershberger and Suri [2001],...

Edge-disjoint paths revisited
Sanjeev Khanna, Chandra Chekuri
Article No.: 46
DOI: 10.1145/1290672.1290683

The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an Ω(m1/2 − &epsis;)-hardness result of Guruswami et al. [2003], and an O(&sqrt;m)...

Packing element-disjoint steiner trees
Joseph Cheriyan, Mohammad R. Salavatipour
Article No.: 47
DOI: 10.1145/1290672.1290684

Given an undirected graph G(V, E) with terminal set TV, the problem of packing element-disjoint Steiner trees is to find the maximum number of Steiner trees that are disjoint on the nonterminal nodes and...

Approximation algorithms and hardness results for cycle packing problems
Michael Krivelevich, Jacques Verstraete Yuster, Zeev Nutov, Raphael Yuster, Mohammad R. Salavatipour
Article No.: 48
DOI: 10.1145/1290672.1290685

The cycle packing number νe(G) of a graph G is the maximum number of pairwise edge-disjoint cycles in G. Computing νe(G) is an NP-hard problem. We present approximation...

Energy-efficient algorithms for flow time minimization
Susanne Albers, Hiroshi Fujiwara
Article No.: 49
DOI: 10.1145/1290672.1290686

We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are...

Improved online algorithms for buffer management in QoS switches
Tomáš Tichý, Wojciech Jawor, Marek Chrobak, Jiří Sgall
Article No.: 50
DOI: 10.1145/1290672.1290687

We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not...

Oblivious routing on node-capacitated and directed graphs
Harald Räcke, Robert D. Kleinberg, Mohammad Taghi Hajiaghayi, Tom Leighton
Article No.: 51
DOI: 10.1145/1290672.1290688

Oblivious routing algorithms for general undirected networks were introduced by Räcke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general...

Routing selfish unsplittable traffic
Vincenzo Auletta, Roberto De Prisco, Giuseppe Persiano, Paolo Penna
Article No.: 52
DOI: 10.1145/1290672.1290689

We consider general resource assignment games involving selfish users/agents in which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which...