Quantifiers and approximation
From MaRDI portal
Publication:1208413
DOI10.1016/0304-3975(93)90259-VzbMath0783.68045MaRDI QIDQ1208413
Desh Ranjan, Alessandro Panconesi
Publication date: 16 May 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ Unnamed Item ⋮ Optimal channel allocation for several types of cellular radio networks ⋮ Normal forms for second-order logic over finite structures, and classification of NP optimization problems ⋮ On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE ⋮ Structure in approximation classes ⋮ Max NP-completeness made easy ⋮ On input read-modes of alternating Turing machines ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Completeness in approximation classes
- The complexity of optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Approximation algorithms for combinatorial problems
- Model theory
- The Complexity of Near-Optimal Graph Coloring
