Abstract
A randomized version of the Clique approximation algorithm by Boppana and Halldórsson is analyzed. The Boppana Halldórsson algorithm is currently the only approximation algorithm for the Clique problem with a non-trivial performance guarantee. This paper presents a class of graphs on which the performance ratio of the randomized version of the algorithm is not better than Ω(√n) with probability greater than 1-1/n ω(1).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Noga Alon, Joel Spencer, and Paul Erdös. The Probabilistic Method. Wiley, 1992.
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In 33rd FOCS, pages 14–23, 1992.
R. Boppana and M. Halldórsson. Approximating maximum independent sets by excluding subgraphs. In SWAT, pages 11–25. Springer Verlag, 1990.
R. Boppana and M. Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT, 32:180–196, 1992.
P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357–368, 1981.
Torben Hagerup and Christine Rub. A guided tour of Chernoff bounds. Information Processing Letters, 33:305–308, 1989.
Mark Jerrum. Large cliques elude the metropolis process. Random Structures and Algorithms, 3(4):347–360, 1992.
Ludek Kučera. The greedy coloring is a bad probabilistic algorithm. Journal of Algorithms, 12:674–684, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peinado, M. (1994). Hard graphs for randomized subgraph exclusion algorithms. In: Schmidt, E.M., Skyum, S. (eds) Algorithm Theory — SWAT '94. SWAT 1994. Lecture Notes in Computer Science, vol 824. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58218-5_26
Download citation
DOI: https://doi.org/10.1007/3-540-58218-5_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58218-2
Online ISBN: 978-3-540-48577-3
eBook Packages: Springer Book Archive