The t- vertex cover problem: Extending the half integrality framework with budget constraints
Abstract
In earlier work we defined a class of integer programs with constraints that involve
up to three variables each and showed how to derive superoptimal half
integral solution to such problems. These solutions can be used under
certain conditions to generate 2-approximations. Here we
extend these results to problems involving budget constraints
that do not conform to the structure of that class. Specifically, we
address the t- vertex cover problem recently studied in the literature.
In this problem the aim is to cover at least t edges in the graph with
minimum weight collection of vertices that are adjacent to these edges.
The technique proposed employs a relaxation of the budget constraint
and a search for optimal dual multiplier assigned to this constraint.
The multipliers can be found substantially more efficiently than with
approaches previously proposed that require the solution of a
linear programming problem using the interior point or ellipsoid
method. Instead of linear programming we use a combinatorial algorithm
solving the minimum cut problem.
Download Information
Click on the following title to view and download the paper in PostScript format.
- The t- vertex cover problem: Extending the half integrality framework with budget constraints (13 pages, 171 KB)
,
- Dorit S. Hochbaum. Procdeedings of APPROX98, Aalborg Denmark, July 1998.
dorit@hochbaum.ieor.berkeley.edu
7/30/98