Polynomially bounded minimization problems which are hard to approximate

DOI10.1007/3-540-56939-1_61zbMath1422.68120OpenAlexW1557755441MaRDI QIDQ4630248

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

Turing machinelinear reduction3CNF formulainput instanceshort computation

Mathematics Subject Classification ID

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

Related Items (7)

The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ Intractability of assembly sequencing: Unit disks in the plane ⋮ Approximating minimum keys and optimal substructure screens ⋮ Approximate solution of NP optimization problems ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Parameterized complexity of conflict-free set cover

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the minimum maximal independence number
• On approximating the minimum independent dominating set
• Completeness in approximation classes
• The complexity of optimization problems
• On the complexity of approximating the independent set problem
• Optimization, approximation, and complexity classes
• Logical definability of NP optimization problems
• Robust trainability of single neurons
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Relations Among Complexity Measures
• On the approximability of the maximum common subgraph problem

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