Solving integer programs over monotone inequalities
in three variables: A framework for half integrality and good approximations
Abstract
We define a class of monotone integer programs with constraints
that involve up to three variables each. A generic constraint in
such integer program is of the form ax-by\leq z+c, where a and
b are nonnegative and the variable z appears only in that
constraint. We devise an algorithm solving such problems in time
polynomial in the length of the input and the range of the
variables U. The solution is obtained from a minimum cut on a
graph with O(nU) nodes and O(mU) arcs where n is the number
of variables of the type x and y and m is the number of
constraints. Our algorithm is also valid for nonlinear objective
functions.
Nonmonotone integer programs are optimization problems with
constraints of the type ax+by\leq z+c without restriction on
the signs of a and b. Such problems are in general NP-hard.
We devise here an algorithm, relying on a transformation to the
monotone case, that delivers half integral superoptimal solutions
in polynomial time. Such solutions provide bounds on the optimum
value that can only be superior to bounds provided by linear
programming relaxation. When the half integral solution can be
rounded to an integer feasible solution, this is a
2-approximate solution. In that the technique is a unified
2-approximation technique for a large class of problems. The
results apply also for general integer programming problems with
worse approximation factors that depend on a quantifier measuring
how far the problem is from the class of problems we describe.
The algorithm described here has a wide array of problem
applications. An additional important consequence of out results
is that nonmonotone problems in the framework are MAX SNP-hard and
at least as hard to approximate as vertex cover.
Problems that are amenable to the analysis provided here are
easily recognized. The analysis itself is entirely technical and
involves manipulating the constraints and transforming them to a
totally unimodular system while losing no more than a factor of
2 in the integrality.
Download Information
Click on the following title to view and download the paper in PostScript format.
Please contact me for the full paper.
hochbaum@ieor.berkeley.edu
12/30/02