Safe approximation and its relation to kernelization

DOI10.1007/978-3-642-28050-4_14MaRDI QIDQ2891346zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Stefan Kratsch, Iyad Kanj

Publication date 15 June 2012

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-28050-4_14

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Polynomial kernelizations for \(\text{MIN} \text{F}^+ \Pi_1\) and \(\text{MAX NP}\)
• Lossy kernelization
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• On problems without polynomial kernels
• A hierarchy of polynomial kernels

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Linear Kernel for Planar Feedback Vertex Set
• A 4k^2 kernel for feedback vertex set
• Algorithms – ESA 2005
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for combinatorial problems
• Approximation properties of NP minimization classes
• Depth-first search and the vertex cover problem
• Nondeterminism within $P^ * $
• On fixed-parameter tractability and approximability of NP optimization problems
• On the Induced Matching Problem
• On the efficiency of polynomial time approximation schemes
• Optimization, approximation, and complexity classes
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial time approximation schemes and parameterized complexity
• Polynomial-time data reduction for dominating set
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Strong computational lower bounds via parameterized complexity
• The complexity of polynomial-time approximation
• Vertex cover: Further observations and further improvements
• Vertex packings: Structural properties and algorithms

Cited in

(3)

• Parameterized (in)approximability of subset problems
• Approximation algorithms inspired by kernelization methods
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds

This page was built for publication: Safe approximation and its relation to kernelization

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