Approximating independent sets in sparse graphs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)

Samenvatting

We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d/log d) approximation due to Halperin. It is also known that no o(d/ log2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results: (i) The natural LP formulation for the problem strengthened by O(log4(d)) levels of the mixed-hierarchy has an integrality gap of Õ(d/log2 d), where Õ(·) ignores some log log d factors. However, our proof is non-constructive, in particular it uses an entropy based approach due to Shearer, and does not give a Õ(d/log2d) approximation algorithm with sub-exponential running time. (ii) We give an O(d/log d) approximation based on polylog(d)-levels of the mixed hierarchy that runs in nO(1) exp(logO(1) d) time, improving upon Halperin's bound by a modest log log d factor. Our algorithm is based on combining Halperin's approach together with an idea used by Ajtai, Erdös, Komlós and Szemerédi to show that Kr-free, degree-d graphs have independent sets of size Or(n log log d/d). Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611973730.1
Originele taal-2Engels
TitelTwenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015)
Plaats van productiePhiladelphia
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
Pagina's1-8
ISBN van geprinte versie978-1-61197-374-7
DOI's
StatusGepubliceerd - 2015
Evenement26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) - Westin San Diego Gaslamp Quarter, San Diego, Verenigde Staten van Amerika
Duur: 4 jan 20156 jan 2015
Congresnummer: 26
http://www.siam.org/meetings/da15/

Congres

Congres26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
Verkorte titelSODA '15
LandVerenigde Staten van Amerika
StadSan Diego
Periode4/01/156/01/15
AnderTwenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Approximating independent sets in sparse graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit