Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time

Michael Krivelevich () and Vu Van H. ()
Additional contact information
Michael Krivelevich: Tel Aviv University
Vu Van H.: University of California-San Diego

Journal of Combinatorial Optimization, 2002, vol. 6, issue 2, No 3, 143-155

Abstract: Abstract The independence number of a graph and its chromatic number are known to be hard to approximate. Due to recent complexity results, unless coRP = NP, there is no polynomial time algorithm which approximates any of these quantities within a factor of n 1−∈ for graphs on n vertices. We show that the situation is significantly better for the average case. For every edge probability p = p(n) in the range n −1/2+∈ ≤ p ≤ 3/4, we present an approximation algorithm for the independence number of graphs on n vertices, whose approximation ratio is O((np)1/2/log n) and whose expected running time over the probability space G(n, p) is polynomial. An algorithm with similar features is described also for the chromatic number. A key ingredient in the analysis of both algorithms is a new large deviation inequality for eigenvalues of random matrices, obtained through an application of Talagrand's inequality.

Keywords: approximation algorithms; average running time; sharp concentration (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1013899527204 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:6:y:2002:i:2:d:10.1023_a:1013899527204

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1013899527204

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().