Geometric optimization and the polynomial hierarchy

DOI10.1016/0304-3975(87)90020-XzbMath0643.68052MaRDI QIDQ1102110

Chanderjit L. Bajaj

Publication date: 1987

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

zbMATH Keywords

polynomial hierarchylocation- allocation problemsoptimization of geometric problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Discrete mathematics in relation to computer science (68R99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• Optimization problems and the polynomial hierarchy
• Optimal packing and covering in the plane are NP-complete
• A comparison of polynomial time reducibilities
• Selected Families of Location Problems
• On the Complexity of Some Common Geometric Location Problems
• Location-Allocation Problems
• Technical Note—Location Theory, Dominance, and Convexity: Some Further Results
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity

This page was built for publication: Geometric optimization and the polynomial hierarchy