Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 51 Issue 3, May 2004

Polynomial-time data reduction for dominating set
Jochen Alber, Michael R. Fellows, Rolf Niedermeier
Pages: 363-384
DOI: 10.1145/990308.990309
Dealing with the NP-complete Dominating Set problem on graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a...

Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel A. Spielman, Shang-Hua Teng
Pages: 385-463
DOI: 10.1145/990308.990310
We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an...

Lower bounds on the bounded coefficient complexity of bilinear maps
Peter Bürgisser, Martin Lotz
Pages: 464-482
DOI: 10.1145/990308.990311
We prove lower bounds of order n log n for both the problem of multiplying polynomials of degree n, and of dividing polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers....

Satisfiability of word equations with constants is in PSPACE
Wojciech Plandowski
Pages: 483-496
DOI: 10.1145/990308.990312
We prove that satisfiability problem for word equations is in PSPACE.

On clusterings: Good, bad and spectral
Ravi Kannan, Santosh Vempala, Adrian Vetta
Pages: 497-515
DOI: 10.1145/990308.990313
We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure....