ملخص
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
!!Conference | 18th 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.