Approximation Algorithms for the Test Cover Problem
journal contributionposted on 01.01.1967 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.