Approximation Algorithms for the Test Cover Problem

K.m.j. de Bontridder, Bjarni V. Halldórsson, Magnús M. Halldórsson, C.a.j. Hurkens, Jan Karel Lenstra, R. Ravi, Leen StougieResearch 2003 · DOI

Abstract

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics.
BibTeX
@inproceedings{bontridder2003approximation,
  author = {K.M.J. de Bontridder and Bjarni V. Halldórsson and Magnús M. Halldórsson and C.A.J. Hurkens and Jan Karel Lenstra and R. Ravi and Leen Stougie},
  title = {{Approximation Algorithms for the Test Cover Problem}},
  booktitle = {Research},
  year = {2003},
  doi = {10.1184/r1/6703901},
}

Loading related content...

Figure