Approximation Algorithms for the Test Cover Problem
journal contributionposted on 01.01.1967, 00:00 by K. M. J. De Bontridder, B. D. Halldórsson, M. M. Halldórsson, C.A.J. Hurkins, J. K. Lenstra, Ramamoorthi Ravi, L. Stougie
Any type of content formally published in an academic journal, usually following a peer-review process.
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.