Geometric Optimization and Computational Complexity
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
Our purpose here is to study problems involving geometric optimization, namely, questions of the type: Is there at least a minimum or at most a maximum number of certain geometric figures, that are within certain distances of other figures (objects). We are also concerned with the optimization of the size of these geometric figures. These problems arise as geometric reductions from various classes of location-allocation optimization problems and are inherently not pure combinatorial. Our primary aim, then, is to discover techniques of dealing with such geometric optimization problems, while adapting to these problems the older combinatorial design and analysis methods. The task of classifying problems accurately in the polynomial hierarchy is one of increasing importance. To solve an optimization problem deterministically it seems that one must solve both an