@inbook{883a30cc51ad4cacb35634ff3c299716,
title = "Approximation of a geometric set covering problem",
abstract = "We consider a special set covering problem. This problem is a generalization of finding a minimum clique cover in an interval graph. When formulated as an integer program, the 0-1 constraint matrix of this integer program can be partitioned into an interval matrix and a special 0-1 matrix with a single 1 per column. We show that the value of this formulation is bounded by 2kk+1 times the value of the LP-relaxation, where k is the maximum row sum of the special matrix. For the “smallest” difficult case, i.e., k = 2, this bound is tight. Also we provide an O(n) 3/2 -approximation algorithm in case k = 2.",
author = "S. Kovaleva and F.C.R. Spieksma",
year = "2001",
doi = "10.1007/3-540-45678-3_42",
language = "English",
isbn = "978-3-540-42985-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "493--501",
editor = "P. Eades and T. Takaoka",
booktitle = "Algorithms and Computation",
address = "Germany",
note = "12th International Symposium on Algorithms and Computation (ISAAC 2001), ISAAC 2001 ; Conference date: 19-12-2001 Through 21-12-2001",
}