D. Bertsimas et Cp. Teo, From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems, OPERAT RES, 46(4), 1998, pp. 503-514
In recent years approximation algorithms based on primal-dual methods have
been successfully applied to a broad class of discrete optimization problem
s. In this paper, we propose a generic primal-dual framework to design and
analyze approximation algorithms for integer programming problems of the co
vering type that uses valid inequalities in its design. The worst-case boun
d of the proposed algorithm is related to a fundamental relationship (calle
d strength) between the set of valid inequalities and the set of minimal so
lutions to the covering problems. In this way, we can construct an approxim
ation 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, gen
eral set covering, intersections of polymatroids, and several network desig
n problems attaining (inmost cases) the best worst-case bound known in the
literature.