Parameterized (in)approximability of subset problems

DOI10.1016/j.orl.2014.03.005zbMath1408.68067arXiv1310.5576OpenAlexW2154918515MaRDI QIDQ1785218

Édouard Bonnet, Vangelis Th. Paschos

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

complexitygraphapproximationparameterized algorithm

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

On subexponential and FPT-time inapproximability

Cites Work

• Non deterministic polynomial optimization problems and their approximations
• Safe Approximation and Its Relation to Kernelization
• On the max min vertex cover Problem
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On Parameterized Approximability
• Parameterized Approximation Problems
• Vertex packings: Structural properties and algorithms

This page was built for publication: Parameterized (in)approximability of subset problems