Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 3 Issue 1, February 2007

Section: 1 - Special Issue on SODA 2002

Foreword to special issue on SODA 2002
David Eppstein
Article No.: 1
DOI: 10.1145/1186810.1186811

The string edit distance matching problem with moves
Graham Cormode, S. Muthukrishnan
Article No.: 2
DOI: 10.1145/1186810.1186812

The edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes, and changes needed to convert R to S. Given a text string t of length n, and a pattern...

Frugal path mechanisms
Aaron Archer, Éva Tardos
Article No.: 3
DOI: 10.1145/1186810.1186813

We consider the problem of selecting a low-cost s - t path in a graph where the edge costs are a secret, known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated...

Tight bounds for worst-case equilibria
Artur Czumaj, Berthold Vöcking
Article No.: 4
DOI: 10.1145/1186810.1186814

We study the problem of traffic routing in noncooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore, their behavior does not have to lead to optimal performance of the...

Section: 1 - Special Issue on SODA 2002

On the difficulty of some shortest path problems
John Hershberger, Subhash Suri, Amit Bhosle
Article No.: 5
DOI: 10.1145/1186810.1186815

We prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph G with...

A data structure for a sequence of string accesses in external memory
Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan
Article No.: 6
DOI: 10.1145/1186810.1186816

We introduce a new paradigm for querying strings in external memory, suited to the execution of sequences of operations. Formally, given a dictionary of n strings S1, …, Sn, we aim at...

Entropy-based bounds for online algorithms
Gopal Pandurangan, Eli Upfal
Article No.: 7
DOI: 10.1145/1186810.1186817

We focus in this work on an aspect of online computation that is not addressed by standard competitive analysis, namely, identifying request sequences for which nontrivial online algorithms are useful versus request sequences for which all...

An improved algorithm for radio broadcast
Michael Elkin, Guy Kortsarz
Article No.: 8
DOI: 10.1145/1186810.1186818

We show that for every radio network G = (V, E) and source sV, there exists a radio broadcast schedule for G of length Rad(G, s) +...

Querying priced information in databases: The conjunctive case
Renato Carmo, Tomás Feder, Yoshiharu Kohayakawa, Eduardo Laber, Rajeev Motwani, Liadan O'Callaghan, Rina Panigrahy, Dilys Thomas
Article No.: 9
DOI: 10.1145/1186810.1186819

Query optimization that involves expensive predicates has received considerable attention in the database community. Typically, the output to a database query is a set of tuples that satisfy certain conditions, and, with expensive predicates,...

Algorithmic aspects of bandwidth trading
Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph (Seffi) Naor
Article No.: 10
DOI: 10.1145/1186810.1186820

We study algorithmic problems that are motivated by bandwidth trading in next-generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed...