You are currently browsing the tag archive for the ‘LP rounding’ tag.
It states that the Minkowski sum of a large number of sets is approximately convex. The clearest statement as well as the nicest proof I am familiar with is due to J. W. S. Cassels. Cassels is a distinguished number theorist who for many years taught the mathematical economics course in the Tripos. The lecture notes are available in a slender book now published by Cambridge University Press.
This central limit like quality of the lemma is well beyond the capacity of a hewer of wood like myself. I prefer the more prosaic version.
Let be a collection of sets in
with
. Denote by
the Minkowski sum of the collection
. Then, every
can be expressed as
where
for all
and
.
How might this be useful? Let be an
0-1 matrix and
with
. Consider the problem
Let be a solution to the linear relaxation of this problem. Then, the lemma yields the existence of a 0-1 vector
such that
and
. One can get a bound in terms of Euclidean distance as well.
How does one do this? Denote each column of the
matrix by
and let
. Let
. Because
and
it follows that
. Thus, by the Lemma,
where each and
. In words,
has at most
fractional components. Now construct a 0-1 vector
from
as follows. If
, set
. If
is fractional, round
upto 1 with probability
and down to zero otherwise. Observe that
and the
. Hence, there must exist a 0-1 vector
with the claimed properties.
The error bound of is to large for many applications. This is a consequence of the generality of the lemma. It makes no use of any structure encoded in the
matrix. For example, suppose
were an extreme point and
a totally unimodular matrix. Then, the number of fractional components of $x^*$ are zero. The rounding methods of Kiralyi, Lau and Singh as well as of Kumar, Marathe, Parthasarthy and Srinivasan exploit the structure of the matrix. In fact both use an idea that one can find in Cassel’s paper. I’ll follow the treatment in Kumar et. al.
As before we start with . For convenience suppose
for all
. As
as has more columns then rows, there must be a non-zero vector
in the kernel of
, i.e.,
. Consider
and
. For
and
sufficiently small,
for all
. Increase
and
until the first time at least one component of
and
is in
. Next select the vector
with probability
or the vector
with probability
. Call the vector selected
.
Now . Furthermore,
has at least one more integer component than
. Let
. Let
be the matrix consisting only of the columns in
and
consist only of the components of
in
. Consider the system
. As long as
has more columns then rows we can repeat the same argument as above. This iterative procedure gives us the same rounding result as the Lemma. However, one can do better, because it may be that even when the number of columns of the matrix is less than the number of rows, the system may be under-determined and therefore the null space is non-empty.
In a sequel, I’ll describe an optimization version of the Lemma that was implicit in Starr’s 1969 Econometrica paper on equilibria in economies with non-convexities.
Recent Comments