Quantifiers and approximation

DOI10.1016/0304-3975(93)90259-VMaRDI QIDQ1208413zbMATH OpenFDO

Authors Alessandro Panconesi, Desh Ranjan

Publication date 16 May 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation schemesoptimization problemsMAX NPMAX \(\Pi_ 1\)RMAX\((k)\)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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)