From Valid Inequalities to Heuristics: A Unified View of Primal-Dual Approximation Algorithms in Covering Problems

Dimitris Bertsimas and Chung-Piaw Teo
Additional contact information
Dimitris Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Chung-Piaw Teo: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1998, vol. 46, issue 4, 503-514

Abstract: In recent years approximation algorithms based on primal-dual methods have been successfully applied to a broad class of discrete optimization problems. In this paper, we propose a generic primal-dual framework to design and analyze approximation algorithms for integer programming problems of the covering type that uses valid inequalities in its design. The worst-case bound of the proposed algorithm is related to a fundamental relationship (called strength) between the set of valid inequalities and the set of minimal solutions to the covering problems. In this way, we can construct an approximation algorithm simply by constructing the required valid inequalities. We apply the proposed algorithm to several problems, such as covering problems related to totally balanced matrices, cyclic scheduling, vertex cover, general set covering, intersections of polymatroids, and several network design problems attaining (in most cases) the best worst-case bound known in the literature.

Keywords: Programming; integer; heuristic (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.4.503 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:4:p:503-514

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().