Browsing Combinatorics and Optimization by Subject "hitting set"
Now showing items 1-2 of 2
-
Covering Problems via Structural Approaches
(University of Waterloo, 2011-09-30)The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been ... -
Piercing axis-parallel boxes
(The Electronic Journal of Combinatorics, 2018)Let F be a finite family of axis-parallel boxes in Rd such that F contains no k + 1 pairwise disjoint boxes. We prove that if F contains a subfamily M of k pairwise disjoint boxes with the property that for every F E F ...