The Approximability and Integrality Gap of Interval Stabbing and Independence Problems

Abstract

Motivated by problems such as rectangle stabbing in the plane, we study the minimum hitting set and maximum independent set problems for families of d-intervals and d-union-intervals. We obtain the following: (1) constructions yielding asymptotically tight lower bounds on the integrality gaps of the associated natural linear programming relaxations; (2) an LP-relative dapproximation for the hitting set problem on d-intervals; (3) a proof that the approximation ratios for independent set on families of 2-intervals and 2-union-intervals can be improved to match tight duality gap lower bounds obtained via topological arguments, if one has access to an oracle for a PPAD-complete problem related to finding Borsuk-Ulam fixed-points.

Publication
Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG)