Improving the Cook et al. proximity bound given integral valued constraints

Abstract: Consider a linear program of the form

m a x; c^{o p} x : A x l e q b

, where

A

is an

m i m e s n

integral matrix. In 1986 Cook, Gerards, Schrijver, and Tardos proved that, given an optimal solution

x^{*}

, if an optimal integral solution

z^{*}

exists, then it may be chosen such that

l e f t V e r t x^{*} - z^{*} i g h t V e r t_{i n f t y} < n D e l t a

, where

D e l t a

is the largest magnitude of any subdeterminant of

A

. Since then an open question has been to improve this bound, assuming that

b

is integral valued too. In this manuscript we show that

n D e l t a

can be replaced with

f r a c n 2 c d o t D e l t a

whenever

n g e q 2

. We also show that, in certain circumstances, the factor

n

can be removed entirely.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: Improving the Cook et al. proximity bound given integral valued constraints