hide
Free keywords:
-
Abstract:
A problem arising in integer linear programming is transforming a solution of
a linear system to an integer one that is "close." The customary model for
investigating such problems is, given a matrix A and a [0,1]-valued vector x,
finding a binary vector y such that ||A(x - y)||∞, the maximum violation of the
constraints, is small. Randomized rounding and the algorithm of Beck and Fiala
are ways to compute such solutions y, whereas linear discrepancy is a lower
bound measure. In many applications one is looking for roundings that, in
addition to being close to the original solution, satisfy some constraints
without violation. The objective of this paper is to investigate such problems
in a unified way. To this aim, we extend the notion of linear discrepancy to
include such hard cardinality constraints. We extend the algorithm of Beck and
Fiala to cope with this setting. If the constraints contain disjoint sets of
variables, the rounding error increases by only a factor of two. We also show
how to generate and derandomize randomized roundings respecting disjoint
cardinality constraints. However, we also provide some examples showing that
additional hard constraints may seriously increase the linear discrepancy. In
particular, we show that the c-color linear discrepancy of a totally unimodular
matrix can be as high as Ω(log c).
