Search ACM DL

Search Issue

enter search term and/or author name

**Editorial note**

Susanne Alber

Article No.: 57

DOI: 10.1145/1824777.1824778

**Foreword to special issue on SODA 2008**

Mohammad T. Hajiaghayi, Shang-Hua Teng

Article No.: 58

DOI: 10.1145/1824777.1824793

**Clustering for metric and nonmetric distance measures**

Marcel R. Ackermann, Johannes Blömer, Christian Sohler

Article No.: 59

DOI: 10.1145/1824777.1824779

We study a generalization of the *k*-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set *P* of size *n*, our goal is to find a set *C* of size *k* such that the sum of errors...

**A local algorithm for finding dense subgraphs**

Reid Andersen

Article No.: 60

DOI: 10.1145/1824777.1824780

We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph *G*, a starting vertex *v*, and a parameter...

**Finding one tight cycle**

Sergio Cabello, Matt Devos, Jeff Erickson, Bojan Mohar

Article No.: 61

DOI: 10.1145/1824777.1824781

A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in...

**On the bichromatic k-set problem**

Timothy M. Chan

Article No.: 62

DOI: 10.1145/1824777.1824782

We study a bichromatic version of the well-known *k-set problem*: given two sets *R* and *B* of points of total size *n* and an integer *k*, how many subsets of the form *(R*∩ *h*) ∪ (*B*∖...

**Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm**

Kenneth L. Clarkson

Article No.: 63

DOI: 10.1145/1824777.1824783

The problem of maximizing a concave function *f(x)* in the unit simplex Δ can be solved approximately by a simple greedy algorithm. For given *k*, the algorithm can find a point *x*_{(k)} on a...

**A near-linear-time algorithm for computing replacement paths in planar directed graphs**

Yuval Emek, David Peleg, Liam Roditty

Article No.: 64

DOI: 10.1145/1824777.1824784

Let (*G* = (*V(G)*,*E(G)*)) be a directed graph with nonnegative edge lengths and let *P* be a shortest path from *s* to *t* in *G*. In the *replacement paths* problem we are required to compute for...

**Two-phase greedy algorithms for some classes of combinatorial linear programs**

Ulrich Faigle, Britta Peis

Article No.: 65

DOI: 10.1145/1824777.1824785

We present greedy algorithms for some classes of combinatorial packing and cover problems within the general formal framework of Hoffman and Schwartz' lattice polyhedra. Our algorithms compute in a first phase Monge solutions for the associated...

**On distributing symmetric streaming computations**

Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina

Article No.: 66

DOI: 10.1145/1824777.1824786

A common approach for dealing with large datasets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive datasets, however, even making a single pass over the data is prohibitive. Therefore,...

**Geodesic delaunay triangulations in bounded planar domains**

Steve Y. Oudot, Leonidas J. Guibas, Jie Gao, Yue Wang

Article No.: 67

DOI: 10.1145/1824777.1824787

We introduce a new feature size for bounded domains in the plane endowed with an intrinsic metric. Given a point *x* in a domain *X*, the *systolic feature size* of *X* at *x* measures half the length of the shortest loop...

**Fast asynchronous Byzantine agreement and leader election with full information**

Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani

Article No.: 68

DOI: 10.1145/1824777.1824788

We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past...

**Lower-bounded facility location**

Zoya Svitkina

Article No.: 69

DOI: 10.1145/1824777.1824789

We study the lower-bounded facility location problem which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this...

**Nondecreasing paths in a weighted graph or**: How to optimally read a train schedule

Virginia Vassilevska Williams

Article No.: 70

DOI: 10.1145/1824777.1824790

A travel booking office has timetables giving arrival and departure times for all scheduled trains, including their origins and destinations. A customer presents a starting station and demands a route with perhaps several train connections taking...

**Hausdorff distance under translation for points and balls**

Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Yusu Wang

Article No.: 71

DOI: 10.1145/1824777.1824791

We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the article, we consider two sets *A,B* of balls in R^{d}, *d*=2,3, and wish to find a translation *t* that...

**Finding equitable convex partitions of points in a polygon efficiently**

John Gunnar Carlsson, Benjamin Armbruster, Yinyu Ye

Article No.: 72

DOI: 10.1145/1824777.1824792

Previous work has developed algorithms for finding an equitable convex partition that partitions the plane into *n* convex pieces each containing an equal number of red and blue points. Motivated by a vehicle routing heuristic, we look at a...