ملخص
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 |
المدة | ٩/٠٩/٢٠ → ١٠/٠٩/٢٠ |
ملاحظة ببليوغرافية
Publisher Copyright:© 2021, Springer Nature Switzerland AG.