Recommendations
- A note on the descriptive complexity of maximization problems
- A note on the approximation of the MAX CLIQUE problem
- scientific article; zbMATH DE number 515727
- scientific article; zbMATH DE number 1559517
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
Cites work
- scientific article; zbMATH DE number 4155842 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Approximation algorithms for combinatorial problems
- Completeness in approximation classes
- Model theory
- Non deterministic polynomial optimization problems and their approximations
- The Complexity of Near-Optimal Graph Coloring
- The complexity of optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
Cited in
(25)- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Normal forms for second-order logic over finite structures, and classification of NP optimization problems
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- The approximability of non-Boolean satisfiability problems and restricted integer programming
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Frameworks for logically classifying polynomial-time optimisation problems
- scientific article; zbMATH DE number 2079029 (Why is no real title available?)
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Maximizing agreements with one-sided error with applications to heuristic learning
- Maximizing agreements with one-sided error with applications to heuristic learning
- Max NP-completeness made easy
- Two logical hierarchies of optimization problems over the real numbers
- Structure in approximation classes
- Optimal channel allocation for several types of cellular radio networks
- Logical definability of NP optimization problems
- On quantitative approximation
- Quantifying over the reals
- scientific article; zbMATH DE number 4024790 (Why is no real title available?)
- AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Approximation properties of NP minimization classes
- scientific article; zbMATH DE number 515727 (Why is no real title available?)
- Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
- MNP: A class of NP optimization problems
- On input read-modes of alternating Turing machines
This page was built for publication: Quantifiers and approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208413)