Text

Distance-Sparsity Transference for Vertices of Corner Polyhedra

We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it implies that for any vertex ${x}^*$ of an integer feasible knapsack polytope ${P}({a}, { b})=\{{x} \in {\mathbb R}^n_{\ge 0}: {a}^\top{x}={ b}\}$, ${a}\in {\mathbb Z}^n_{>0}$, there exists an integer point ${z}^*\in {P}({a}, { b})$ such that, denoting by $s$ the size of the support of ${z}^*$ and assuming $s>0$, $ \|{x}^{*}-{z}^{*}\|_{\infty} \,{2^{s-1}}/{s} < \|{a}\|_{\infty}\,, $ where $\|\cdot\|_{\infty}$ stands for the $\ell_{\infty}$-norm. The bound gives an exponential in $s$ improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.


Read More: https://epubs.siam.org/doi/abs/10.1137/20M1353228

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.31 No.1 January-March 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 200 - 216

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

SPARSITY
INTEGER PRGRAMMING
PROXIMITY
CORNER POLYHEDRA
KNAPSACK POLYTOPE

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Iskander Aliev, Marcel Celaya, Martin Henk, Aled Williams

Versi lain/terkait

Lampiran Berkas

Komentar