Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems

Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We show that Set-Cover on instances with N elements cannot be approximated within (1 - γ) ln N -factor in time exp(Nγ - δ), for any 0 < γ< 1 and any δ> 0, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan, Kowalik, and Wykurz [6] of (1 - γ) ln N -factor in time exp(O(Nγ) ). The lower bound is obtained by extracting a standalone reduction from Label-Cover to Set-Cover from the work of Moshkovitz [18], and applying it to a different PCP theorem than done there. We also obtain a tighter lower bound when conditioning on the Projection Games Conjecture. We also treat three problems (Directed Steiner Tree, Submodular Cover, and Connected Polymatroid) that strictly generalize Set-Cover. We give a (1 - γ) ln N -approximation algorithm for these problems that runs in exp(O~ (Nγ) ) time, for any 1 / 2 ≤ γ< 1.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation and Online Algorithms - 18th International Workshop, WAOA 2020, Revised Selected Papers
المحررونChristos Kaklamanis, Asaf Levin
ناشرSpringer Science and Business Media Deutschland GmbH
الصفحات159-173
عدد الصفحات15
رقم المعيار الدولي للكتب (المطبوع)9783030808785
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2021
منشور خارجيًانعم
الحدث18th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Virtual, Online
المدة: ٩ سبتمبر ٢٠٢٠١٠ سبتمبر ٢٠٢٠

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت12806 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference18th International Workshop on Approximation and Online Algorithms, WAOA 2019
المدينةVirtual, Online
المدة٩/٠٩/٢٠١٠/٠٩/٢٠

ملاحظة ببليوغرافية

Funding Information:
The work of Marek Cygan is part of a project TOTAL that has received funding from the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement No 677651). Magnús Halldórsson is partially supported by Icelandic Research Fund grant 174484-051. Guy Kortsarz is partially supported by NSF grants 1540547 and 1910565.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

بصمة

أدرس بدقة موضوعات البحث “Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا