Time-approximation trade-offs for inapproximable problems
From MaRDI portal
Publication:1678175
DOI10.1016/j.jcss.2017.09.009zbMath1380.68440OpenAlexW1694364829MaRDI QIDQ1678175
Édouard Bonnet, Vangelis Th. Paschos, Michael Lampis
Publication date: 14 November 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5723/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (9)
From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Unnamed Item ⋮ In)approximability of Maximum Minimal FVS ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ (In)approximability of maximum minimal FVS ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Moderate exponential-time algorithms for scheduling problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Approximating the minimum maximal independence number
- Exact and approximate bandwidth
- Parameterized approximation of dominating set problems
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Which problems have strongly exponential complexity?
- Fast algorithms for min independent dominating set
- Capacitated domination faster than \(O(2^n)\)
- Parameterized Approximation via Fidelity Preserving Transformations
- Fixed-Parameter and Approximation Algorithms: A New Look
- New Inapproximability Bounds for TSP
- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- Two-query PCP with subconstant error
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- Lossy kernelization
- On the hardness of approximating minimization problems
- Analytical approach to parallel repetition
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- Some optimal inapproximability results
This page was built for publication: Time-approximation trade-offs for inapproximable problems
