Vi studerar om Vertex Cover och Independent Set på grad d grafer. Vi bevisar att: • Vertex Cover är unik spel-hård att approximera till inom en faktor 2 − Detta exakt matchar algoritmiska resultatet av Halperin [1] upp till o d (1) termen. • Independent Set är unik spel-hård att approximera till inom en faktor O( d log 2 d ). Detta förbättrar d log O(1) (d) Unika Spel hårdhet resultat av Samorodnitsky och Trevisan [2]. Dessutom är vårt resultat inte beroende av byggandet av en fråge effektiv PCP som i [2]. 2009 24:e årliga IEEE-konferensen om beräkningskomplexitet 978-0-7695-3717-7/09 $25.00
Detta matchar det oåtkomliga resultat känt, upp till dubbelt-logaritmiska faktorer, som innehar antagandet den unika spel Conjecture REF.
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
{'venue': '2009 24th Annual IEEE Conference on Computational Complexity', 'journal': '2009 24th Annual IEEE Conference on Computational Complexity', 'mag_field_of_study': ['Mathematics', 'Computer Science']}