Quantifiers and approximation

DOI10.1016/0304-3975(93)90259-VzbMATH Open0783.68045MaRDI QIDQ1208413FDOQ1208413

Authors: Alessandro Panconesi, Desh Ranjan 

Publication date: 16 May 1993

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• The complexity of optimization problems
• Model theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Completeness in approximation classes
• Non deterministic polynomial optimization problems and their approximations
• The Complexity of Near-Optimal Graph Coloring
• Toward a unified approach for the classification of NP-complete optimization problems
• Title not available (Why is that?)

Cited In (25)

• 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
• Frameworks for logically classifying polynomial-time optimisation problems
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Title not available (Why is that?)
• 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
• Structure in approximation classes
• Two logical hierarchies of optimization problems over the real numbers
• Max NP-completeness made easy
• Optimal channel allocation for several types of cellular radio networks
• Logical definability of NP optimization problems
• Title not available (Why is that?)
• AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS
• On quantitative approximation
• Quantifying over the reals
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Approximation properties of NP minimization classes
• Title not available (Why is that?)
• MNP: A class of NP optimization problems
• Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
• On input read-modes of alternating Turing machines
• Complexity and approximability of quantified and stochastic constraint satisfaction problems

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)