ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 6 Issue 4, August 2010

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 (Rh) ∪ (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 Rd, 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...