Technical Report CS-2000-10

 TR#: CS-2000-10 Class: CS Title: On the Equivalence Between the Primal-Dual Schema and the Local-Ratio Technique Authors: Reuven Bar-Yehuda and Dror Rawitz PDF CS-2000-10.pdf Abstract: The \emph{Primal-Dual Schema} and the \emph{Local-Ratio Technique} were used to construct many approximation algorithms for $\NP$-hard problems during the last two decades (especially since the beginning of the nineties). We present two relatively simple generic approximation frameworks, one for each approach, which extend known approximation frameworks for covering problems. Both frameworks can be used to approximate maximization problems as well as minimization problems. Furthermore, they are not limited to linear integer programs. One of the main features in both approaches is that they leave room to exploit the combinatorial structure of the problem at hand, and, therefore, usually yield efficient and simple algorithms. While the primal-dual schema uses the construction of valid inequalities to that end, the local-ratio technique utilizes weight functions. We show that the two notions are one and the same, and, by using both frameworks, that the two approaches are equivalent (with respect to a wide family of algorithms). Among other things this equivalence implies that the integrality gap of an integer program is valid as a bound to the approximation ratio when working with the local-ratio technique. Finally, we demonstrate our generic algorithms on a variety of problems. 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/cgi-bin/tr-info.cgi/2000/CS/CS-2000-10), rather than to the URL of the PDF files directly. The latter URLs may change without notice.