This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Correa, J. R. Articles by Levin, A. Search for Related Content

Monotone Covering Problems with an Additional Covering Constraint

Departamento de Ingeniería Industrial, Universidad de Chile, Santiago, Chile
Faculty of Industrial Engineering and Management, The Technion, 32000 Haifa, Israel
jcorrea{at}dii.uchile.cl, http://www.dii.uchile.cl/jcorrea
levinas{at}tx.technion.ac.il, http://mscc.huji.ac.il/levinas

We provide preliminary results regarding the existence of a polynomial time approximation scheme (PTAS) for minimizing a linear function over a 0/1 covering polytope which is integral, with one additional covering constraint. Our algorithm is based on extending the methods of Goemans and Ravi for the constrained minimum spanning tree problem and, in particular, implies the existence of a PTAS for several covering integer programming problems with a totally unimodular constraint matrix. These include the cases when the columns of the constraint matrix either: have at most two nonzero elements; are incidence vectors of a laminar family; or have consecutive ones and no column is contained in another.

Key Words: Lagrangian relaxation; approximation algorithms; covering integer programs
History: Received: July 23, 2007; revision received: August 7, 2008;