Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 5 Issue 3, July 2009

Foreword to special issue on SODA 2007
Harold Gabow
Article No.: 25
DOI: 10.1145/1541885.1541886

Making deterministic signatures quickly
Milan Ružić
Article No.: 26
DOI: 10.1145/1541885.1541887

We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the word RAM, the practical RAM,...

Compacting cuts: A new linear formulation for minimum cut
Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, Ojas Parekh
Article No.: 27
DOI: 10.1145/1541885.1541888

For a graph (V,E), existing compact linear formulations for the minimum cut problem require Θ(|V||E|) variables and constraints and can be interpreted as a composition of...

Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
Yoav Giora, Haim Kaplan
Article No.: 28
DOI: 10.1145/1541885.1541889

We consider the dynamic vertical ray shooting problem against horizontal disjoint segments, that is, the task of maintaining a dynamic set S of n nonintersecting horizontal line segments in the plane under a query that reports the...

Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition
David Eppstein
Article No.: 29
DOI: 10.1145/1541885.1541890

We provide efficient constant-factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the...

Minimizing movement
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, Morteza Zadimoghaddam
Article No.: 30
DOI: 10.1145/1541885.1541891

We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or...

An O(n log n) approximation scheme for Steiner tree in planar graphs
Glencora Borradaile, Philip Klein, Claire Mathieu
Article No.: 31
DOI: 10.1145/1541885.1541892

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n).


Near-optimal algorithms for maximum constraint satisfaction problems
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Article No.: 32
DOI: 10.1145/1541885.1541893

In this article, we present two approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP).

Given a (1 − ϵ) satisfiable 2CSP our first algorithm finds...

Instability of FIFO in the permanent sessions model at arbitrarily small network loads
Matthew Andrews
Article No.: 33
DOI: 10.1145/1541885.1541894

We show that for any r > 0, there is a network of First-In-First-Out servers and a fixed set of sessions such that:

—The network load is r with respect to the permanent sessions model with bounded arrivals.