Search ACM DL

Search Issue

enter search term and/or author name

Section:

**Editorial to the Special Issue on SODA'12**

Yuval Rabani, Andrea Richa, Jared Saia, David P. Woodruff

Article No.: 1

DOI: 10.1145/2846001

**Approximation Algorithms and Hardness of the k-Route Cut Problem**

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou

Article No.: 2

DOI: 10.1145/2644814

We study the *k*-route cut problem: given an undirected edge-weighted graph *G* = (*V*, *E*), a collection {(*s*_{1}, *t*_{1}), (*s*_{2}, *t*_{2}), …,...

**Computing the Distance between Piecewise-Linear Bivariate Functions**

Guillaume Moroz, Boris Aronov

Article No.: 3

DOI: 10.1145/2847257

We consider the problem of computing the distance between two piecewise-linear bivariate functions *f* and *g* defined over a common domain *M*, induced by the *L*_{2} norm—that is, ‖ *f* −...

**Fast Zeta Transforms for Lattices with Few Irreducibles**

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, Pekka Parviainen

Article No.: 4

DOI: 10.1145/2629429

We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with *v* elements, *n* of which are nonzero and...

**Width of Points in the Streaming Model**

Alexandr Andoni, Huy L. Nguyêݱn

Article No.: 5

DOI: 10.1145/2847259

In this article, we show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume that the stream contains both insertions of points and deletions of points to a set *S*, and the...

**Bypassing UGC from Some Optimal Geometric Inapproximability Results**

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Article No.: 6

DOI: 10.1145/2737729

The Unique Games Conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for *none* of these results a reverse reduction to Unique Games is known, the assumption of bijective...

Section: **Special Issue on SODA'12**

**Simple Deterministic Algorithms for Fully Dynamic Maximal Matching**

Ofer Neiman, Shay Solomon

Article No.: 7

DOI: 10.1145/2700206

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) *n*-vertex graphs using a trivial deterministic algorithm with a worst-case update time of *O*(*n*). No deterministic algorithm...

**On the k-Independence Required by Linear Probing and Minwise Independence**

Mihai Pǎtraşcu, Mikkel Thorup

Article No.: 8

DOI: 10.1145/2716317

We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of Pagh et al. [2009]. More precisely, we construct a random 4-independent hash function yielding expected...

**Sparse Sums of Positive Semidefinite Matrices**

Marcel K. De Carli Silva, Nicholas J. A. Harvey, Cristiane M. Sato

Article No.: 9

DOI: 10.1145/2746241

Many fast graph algorithms begin by preprocessing the graph to improve its sparsity. A common form of this is spectral sparsification, which involves removing and reweighting the edges of the graph while approximately preserving its spectral...

**Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets**

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Article No.: 10

DOI: 10.1145/2746226

Consider the following problem: given a set system (*U*, Ω) and an edge-weighted graph *G* = (*U*, *E*) on the same universe *U*, find the set *A* ∈ Ω such that the Steiner tree cost with...

**Dominator Tree Certification and Divergent Spanning Trees**

Loukas Georgiadis, Robert E. Tarjan

Article No.: 11

DOI: 10.1145/2764913

How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. Alternatively, one can check that the output produced for a...

**Approximating the Diameter of Planar Graphs in Near Linear Time**

Oren Weimann, Raphael Yuster

Article No.: 12

DOI: 10.1145/2764910

We present a (1 + ϵ)-approximation algorithm running in *O*(*f*(ϵ) · *n*log ^{4}*n*) time for finding the diameter of an undirected planar graph with *n* vertices and with nonnegative edge...