Polynomially bounded minimization problems which are hard to approximate

DOI10.1007/3-540-56939-1_61MaRDI QIDQ4630248zbMATH OpenOpenAlexFDO

Authors Viggo Kann

Publication date 29 March 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-56939-1_61

zbMATH Keywords

3CNF formulainput instancelinear reductionshort computationTuring machine

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 751135
• On the hardness of approximating minimization problems
• Near minimax polynomial approximation
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• scientific article; zbMATH DE number 1865680
• scientific article; zbMATH DE number 953034
• Norm bounds and underestimators for unconstrained polynomial integer minimization
• Complexity of approximating bounded variants of optimization problems
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
• Minimizing polynomials on noncompact sets

Cites work

• Approximating the minimum maximal independence number
• Completeness in approximation classes
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Logical definability of NP optimization problems
• On approximating the minimum independent dominating set
• On the approximability of the maximum common subgraph problem
• On the complexity of approximating the independent set problem
• Optimization, approximation, and complexity classes
• Relations Among Complexity Measures
• Robust trainability of single neurons
• The complexity of optimization problems

Cited in

(11)

• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Minimizer Extraction in Polynomial Optimization Is Robust
• scientific article; zbMATH DE number 751135 (Why is no real title available?)
• Exploring the kernelization borders for hitting cycles
• Intractability of assembly sequencing: unit disks in the plane
• Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems
• Parameterized complexity of conflict-free set cover
• Conflict free version of covering problems on graphs: classical and parameterized
• Approximating minimum keys and optimal substructure screens
• Approximate solution of NP optimization problems

This page was built for publication: Polynomially bounded minimization problems which are hard to approximate

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