Time-approximation trade-offs for inapproximable problems

DOI10.4230/LIPICS.STACS.2016.22MaRDI QIDQ4601874zbMATH OpenFDO

Authors Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1502.05828

zbMATH Keywords

approximation algorithmcomplexityinapproximabilitypolynomial approximationreductionsubexponential approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Time-approximation trade-offs for inapproximable problems
• (In)approximability of maximum minimal FVS
• New tools and connections for exponential-time approximation
• Exponential-time approximation of weighted set cover
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

Cited in

(7)

• Time-approximation trade-offs for inapproximable problems
• New tools and connections for exponential-time approximation
• Maximum minimal vertex cover parameterized by vertex cover
• Maximum minimal vertex cover parameterized by vertex cover
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• Exponential-time approximation of weighted set cover

This page was built for publication: Time-approximation trade-offs for inapproximable problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601874)