direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprint 05-2020

Proximity bounds for random integer programs

Source file is available as :   Portable Document Format (PDF)

Author(s) : Marcel Celaya , Martin Henk

Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 05-2020

MSC 2000

90C10 Integer programming
52C07 Lattices and convex bodies in $n$ dimensions

Abstract :
We study proximity bounds within a natural model of random integer programs of the type max cx : Ax = b, x >= 0. We prove that (up to a constant depending on the dimension n) the proximity is generally bounded by Delta_m(A)^1/(n-m), where is m the rank of A and Delta_m(A) is the maximal absolute value of an m x m subdeterminant of A. This is significantly better than the best deterministic bounds which are linear in Delta_m(A).

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe