Inhalt des Dokuments
Preprint 37-2003
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Minimizing the Stabbing Number of Matchings, Trees, and Triangulations
- Authors
- Publication
- Appears in Symposium on Discrete Algorithms (SODA 2004)
- Classification
-
MSC: primary: 90C27 Combinatorial optimization secondary: 68Q25 Analysis of algorithms and problem complexity 68Q17 Computational difficulty of problems 90C05 Linear programming - Keywords
-
Stabbing number, crossing number, matching, spanning tree, triangulation, complexity, linear programming relaxation, iterated rounding
- Abstract
-
The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. We investigate problems of finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of points. The complexity of these problems has been a long-standing open problem; in fact, it is one of the original 30 outstanding open problems in computational geometry on the list by Demaine, Mitchell, and O'Rourke.We show that minimum stabbing problems are NP-complete. We also show that an iterated rounding technique is applicable for matchings and spanning trees of minimum stabbing number by showing that there is a polynomially solvable LP-relaxation that has fractional solutions with at least one heavy edge. This suggests constant-factor approximations. Our approach uses polyhedral methods that are related to another open problem (from a combinatorial optimization list), in combination with geometric properties. We also demonstrate that the resulting techniques are practical for actually solving problems with up to several hundred points optimally or near-optimally.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe