AbstractA randomized version of the MAXCLIQUE approximation algorithm by Boppana and Halldórsson is analyzed. The Boppana Halldórsson algorithm has the best performance guarantee currently known for the MAXCLIQUE problem. This paper presents a class of graphs on which the performance ratio of the randomized version of the algorithm is not better than Omega(sqrt(n)) with probability greater than 1 - 1/nomega(1).
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory; G.3 [Probability and Statistics]
Additional Key Words and Phrases: approximation algorithms, MAXCLIQUE, randomization
Selected papers that cite this one
- Ari Juels and Marcus Peinado. Hiding cliques for cryptographic security. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 678-684, San Francisco, California, 25-27 January 1998.
Selected references
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Mihir Bellare and Madhu Sudan. Improved non-approximability results. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 184-193, Montréal, Québec, Canada, 23-25 May 1994.