Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
New Tools and Connections for Exponential-Time Approximation
Eindhoven Univ Technol, Eindhoven, Netherlands..
Aalto Univ, Helsinki, Finland..
Shanghai Univ Finance & Econ, Shanghai, Peoples R China..
KTH, Skolan för elektroteknik och datavetenskap (EECS), Teoretisk datalogi, TCS.ORCID-id: 0000-0003-4468-2675
Visa övriga samt affilieringar
2019 (Engelska)Ingår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 81, nr 10, s. 3993-4009Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r > 1, and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of 1. r for maximum independent set in O*(exp((O) over tilde (n/r log(2) r + r log(2) r))) time, 2. r for chromatic number in O*(exp((O) over tilde (n/r log r + r log(2) r))) time, 3. (2 - 1/r) for minimum vertex cover in O*(exp(n/r(Omega(r)))) time, and 4. (k - 1/r) for minimum k-hypergraph vertex cover in O*(exp(n/(kr)(Omega(kr)))) time. (Throughout, (O) over tilde and O* omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O*(2n/r) (Bourgeois et al. in Discret Appl Math 159(17): 1954-1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp(n(1-o(1))/r(1+o(1))) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370-379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O*(2n/r) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP (Chan in J. ACM 63(3): 27: 1-27: 32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23: 128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).

Ort, förlag, år, upplaga, sidor
SPRINGER , 2019. Vol. 81, nr 10, s. 3993-4009
Nyckelord [en]
Approximation algorithms, PCP's, Exponential time algorithms
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:kth:diva-259411DOI: 10.1007/s00453-018-0512-8ISI: 000482896500007PubMedID: 31496549Scopus ID: 2-s2.0-85053412910OAI: oai:DiVA.org:kth-259411DiVA, id: diva2:1354062
Anmärkning

QC 20190924

Tillgänglig från: 2019-09-24 Skapad: 2019-09-24 Senast uppdaterad: 2019-09-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextPubMedScopus

Personposter BETA

Na Nongkai, Danupon

Sök vidare i DiVA

Av författaren/redaktören
Na Nongkai, Danupon
Av organisationen
Teoretisk datalogi, TCS
I samma tidskrift
Algorithmica
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
pubmed
urn-nbn

Altmetricpoäng

doi
pubmed
urn-nbn
Totalt: 29 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf