enter search term and/or author name
Polynomial-time data reduction for dominating set
Jochen Alber, Michael R. Fellows, Rolf Niedermeier
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
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
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
We prove that satisfiability problem for word equations is in PSPACE....
On clusterings: Good, bad and spectral
Ravi Kannan, Santosh Vempala, Adrian Vetta
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....