Search ACM DL

Search Issue

enter search term and/or author name

**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 Ω(*m*^{1/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 *T* ⊆ *V*, 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...