Some Easy and Some Not so Easy Geometric Optimization Problems

摘要

We survey complexity and approximability results for certain families of geometric optimization problems. We explain a generic approximation approach for maximization problems that is built around norms with polyhedral unit balls, and we pose a multitude of open problems.