- importsource = "00045411-2011-05.txt"
- Artículo:
Smoothed Analysis of the k-Means Method
- Autor:
David Arthur
Bodo Manthey
Heiko Röglin
- Página:
19
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
5
- Periodo:
Octubre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-05.txt
- Documento número 253043
- Actualizado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Creado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Enlace directo
- Artículo:
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 practical ... expand Hardness of Approximating Flow and Job Shop Scheduling Problems
- Autor:
Monaldo Mastrolilli
Ola Svensson
- Resumen:
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 inapproximability ... expand
- Página:
20
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
5
- Periodo:
Octubre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-05.txt
- Documento número 253044
- Actualizado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Creado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Enlace directo
- Artículo:
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Autor:
Mohammadhossein Bateni
Mohammadtaghi Hajiaghayi
Dániel Marx
- Resumen:
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 such ... expand
- Página:
21
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
5
- Periodo:
Octubre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-05.txt
- Documento número 253045
- Actualizado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Creado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Enlace directo
- Artículo:
Invited Articles Foreword
- Autor:
Victor Vianu
- Página:
22
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
5
- Periodo:
Octubre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-05.txt
- Documento número 253046
- Actualizado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Creado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Enlace directo
- Artículo:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
- Autor:
Leonid Barenboim
Michael Elkin
- Resumen:
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 G. ... expand
- Página:
23
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
5
- Periodo:
Octubre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-05.txt
- Documento número 253047
- Actualizado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Creado el martes, 23 de mayo de 2017 03:53:21 p. m.
- Enlace directo
