enter search term and/or author name
The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between...
Hardness of Approximating Flow and Job Shop Scheduling Problems
Monaldo Mastrolilli, Ola Svensson
Article No.: 20
We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known...
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, Dániel Marx
Article No.: 21
We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for...
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Leonid Barenboim, Michael Elkin
Article No.: 23
Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in...