Back to Search
Start Over
Time-Approximation Trade-offs for Inapproximable Problems
- Source :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, Elsevier, 2018, 92, pp.171-180, Journal of Computer and System Sciences, Elsevier, 2018, 92, pp.171-180. ⟨10.1016/j.jcss.2017.09.009⟩, Journal of Computer and System Sciences, 2018, 92, pp.171-180. ⟨10.1016/j.jcss.2017.09.009⟩, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Feb 2016, Orléans, France. pp.22:1-22:14, ⟨10.4230/LIPIcs.STACS.2016.22⟩
- Publication Year :
- 2015
-
Abstract
- In this paper we focus on problems which do not admit a constant-factor approximation in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set, Max Induced Path, Forest and Tree, for any r(n), a simple, known scheme gives an approximation ratio of r in time roughly rn/r. We show that, for most values of r, if this running time could be significantly improved the ETH would fail. For Max Minimal Vertex Cover we give a nontrivial √r-approximation in time 2n/r. We match this with a similarly tight result. We also give a log r-approximation for Min ATSP in time 2n/r and an r-approximation for Max Grundy Coloring in time rn/r. Furthermore, we show that Min Set Cover exhibits a curious behavior in this superpolynomial setting: for any δ > 0 it admits an mδ-approximation, where m is the number of sets, in just quasi-polynomial time. We observe that if such ratios could be achieved in polynomial time, the ETH or the Projection Games Conjecture would fail. © Édouard Bonnet, Michael Lampis and Vangelis Th. Paschos; licensed under Creative Commons License CC-BY.
- Subjects :
- FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Polynomial
Induced path
Computer Networks and Communications
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Vertex cover
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
Hardness of approximation
01 natural sciences
Theoretical Computer Science
Combinatorics
Exponential algorithms
Dominating set
Computer Science - Data Structures and Algorithms
Polynomial and Subexponential Approximation
0202 electrical engineering, electronic engineering, information engineering
Data Structures and Algorithms (cs.DS)
[INFO]Computer Science [cs]
Approximation
Time complexity
ComputingMilieux_MISCELLANEOUS
Reduction
Mathematics
000 Computer science, knowledge, general works
Applied Mathematics
Approximation algorithm
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Set cover problem
021107 urban & regional planning
Complexity
Sub-exponential algorithms
Approximation algorithms
Computer Science - Computational Complexity
Computational Theory and Mathematics
010201 computation theory & mathematics
Computer Science
020201 artificial intelligence & image processing
Inapproximability
Subjects
Details
- Language :
- English
- ISSN :
- 00220000 and 10902724
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, Elsevier, 2018, 92, pp.171-180, Journal of Computer and System Sciences, Elsevier, 2018, 92, pp.171-180. ⟨10.1016/j.jcss.2017.09.009⟩, Journal of Computer and System Sciences, 2018, 92, pp.171-180. ⟨10.1016/j.jcss.2017.09.009⟩, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Feb 2016, Orléans, France. pp.22:1-22:14, ⟨10.4230/LIPIcs.STACS.2016.22⟩
- Accession number :
- edsair.doi.dedup.....aa7742a00e2e75113c6069f964eb72d1