Geometric optimization and \(D^ P\)-completeness

DOI10.1007/BF02187711zbMath0651.68055OpenAlexW2210827803MaRDI QIDQ1106665

Ming Li, Chanderjit L. Bajaj

Publication date: 1989

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131060

zbMATH Keywords

polynomial hierarchygeometric optimization\(D^ P\)-completenesscomplexity of optimization problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• The algebraic degree of geometric optimization problems
• Optimization problems and the polynomial hierarchy
• Optimal packing and covering in the plane are NP-complete
• A comparison of polynomial time reducibilities
• Second-Order Analysis of Polyhedral Systems in Finite and Infinite Dimensions with Applications to Robust Stability of Variational Inequalities
• Second Order Sufficiency Criteria for a Discrete Optimal Control Problem
• On the Complexity of Some Common Geometric Location Problems
• On the complexity of unique solutions
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity