Approximation algorithms for the test cover problem

Approximation algorithms for the test cover problem

0.00 Avg rating0 Votes
Article ID: iaor20051112
Country: Germany
Volume: 98
Issue: 1/3
Start Page Number: 477
End Page Number: 491
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors:
Keywords: sets
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.

Reviews

Required fields are marked *. Your email address will not be published.