TR#:  CS0920 
Class:  CS 
Title:  One for the Price of Two: A Unified Approach
for Approximating Covering Problems

Authors:  Reuven BarYehuda 
CS0920.pdf  
Abstract:  We present a simple and unified approach for developing and analyzing approximation algorithms for covering problems. We illustrate this on approximation algorithms for the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner Tree and related problems. The main idea can be phrased as follows: iteratively, pay two dollars (at most) to reduce the total optimum by one dollar (at least), so the rate of payment is no more than twice the rate of the optimum reduction. This implies a total payment (i.e., approximation cost ) $\leq$ twice the optimum cost. Our main contribution is based on a formal definition for covering problems, which includes all the above fundamental problems and others. We further extend the Bafna, Berman and Fujito LocalRatio theorem. This extension eventually yields a short generic $r$approximation algorithm which can generate most known approximation algorithms for most covering problems. Using our technique, we present a linear time 2approximation algorithm for the Min CliqueComplement problem. The previous best result was a 4approximation algorithm due to Hochbaum. Another extension of the LocalRatio theorem to randomized algorithms gives a simple proof of Pitt's randomized approximation for Vertex Cover. Using this approach, we develop a modified greedy algorithm, which for Vertex Cover, gives an expected performance ratio $ \leq 2$. 
Copyright  The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information 
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1997/CS/CS0920), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1997
To the main CS technical reports page