- 1.A. Blum. Algorithms for approximate graph coloring. Ph.D. Thesis, Dept. of Electrical Engineering and Computer Science, MIT, 1991. Google ScholarDigital Library
- 2.R. B. Boppana and M. M. Halld6rsson. Approximating maximum independent sets by excluding subgraphs. BIT, 32:180-196, 1992. Google ScholarDigital Library
- 3.L. Engebretsen and j. Holmerin. Clique is hard to approximate within n1-~(I). Manuscript, 1999.Google Scholar
- 4.U. Feige. Randomized graph products, chromatic numbers, and the Lovasz t%function. In Proc. A CM Symposium on Theory of Computing, pages 635-640, 1995. Google ScholarDigital Library
- 5.U. Feige, S. Goldwasser, L. Lovgsz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the A CM, 43:268-292, 1996. Google ScholarDigital Library
- 6.M. M. Hallddrsson. Approximation via partitioning. Res. Report IS-RR-95-OO3F, Japan Advanced Institute of Science and Technology, 1995.Google Scholar
- 7.M. M. Halld6rsson. Approximations of independent sets in graphs. Survey paper, Proc. APPROX '98 Conference, 1998. Google ScholarDigital Library
- 8.J. H~stad. Clique is hard to approximate within n1-~. In Proc. IEEE Symposium on Foundations of Computer Science, pages 627-636, 1996. To appear in Acta Mathematica. Google ScholarDigital Library
- 9.P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences, 37:130-143, 1988. Google ScholarDigital Library
- 10.A. Samorodnitsky and L. Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proc. A CM Symposium on Theory of Computing, 2000. Google ScholarDigital Library
- 11.J. P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff- Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8:223- 250, 1995. Google ScholarDigital Library
- 12.A. Srinivasan. improved approximation guarantees for packing and covering integer programs. SIAM J. Cornput., 29:648-670, 1999. Google ScholarDigital Library
- 13.A. C.-C. Yao. Probabilistic computations: towards a unified measure of complexity. In Proc. IEEE Symposium on Foundations of Computer Science, pages 222- 227, 1977.Google ScholarDigital Library
Index Terms
- The value of strong inapproximability results for clique
Recommendations
On the parameterized complexity of multiple-interval graph problems
Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more ...
Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs
AbstractWe study algorithmic properties of the graph class , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental ...
Linear degree extractors and the inapproximability of max clique and chromatic number
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingA randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant ...
Comments