Search ACM DL

Search Issue

enter search term and/or author name

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