アイテム詳細

要旨

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).