Improving proximity bounds using sparsity

DOI10.1007/978-3-030-53262-8_10MaRDI QIDQ2225054zbMATH OpenOpenAlexFDO

Authors Jon Lee, Joseph Paat, Ingo Stallknecht, Luze Xu

Publication date 4 February 2021

Full work available at URL https://arxiv.org/abs/2001.04659

zbMATH Keywords

mixed integer programmingproximitysparsity

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: We refer to the distance between optimal solutions of integer programs and their linear relaxations as proximity. In 2018, Eisenbrand and Weismantel proved that proximity is independent of the dimension for programs in standard form. We improve their bounds using existing and novel results on the sparsity of integer solutions. We first bound proximity in terms of the largest absolute value of any full-dimensional minor in the constraint matrix, and this bound is tight up to a polynomial factor in the number of constraints. We also give an improved bound in terms of the largest absolute entry in the constraint matrix, after efficiently transforming the program into an equivalent one. Our results are stated in terms of general sparsity bounds, so any new results on sparse solutions immediately improves our work. Generalizations to mixed integer programs are also discussed.

Recommendations

• Distance-sparsity transference for vertices of corner polyhedra
• Proximity in concave integer quadratic programming
• Proximity bounds for random integer programs
• Proximity bounds for random integer programs
• Tightness of sensitivity and proximity bounds for integer linear programs

Cited in

(18)

• An FPTAS for the -modular multidimensional knapsack problem
• Proximity in concave integer quadratic programming
• On lattice point counting in -modular polyhedra
• Improving the Cook et al. proximity bound given integral valued constraints
• Sparse Sourcewise and Pairwise Distance Preservers
• Distance-sparsity transference for vertices of corner polyhedra
• Advances on strictly \(\varDelta \)-modular IPs
• A colorful Steinitz lemma with application to block-structured integer programs
• On -modular integer linear problems in the canonical form and equivalent problems
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• Advances on strictly -modular IPs
• Sensitivity analysis for mixed binary quadratic programming
• Sparsity and integrality gap transference bounds for integer programs
• Sparsity and proximity transference in integer programming
• Sensitivity analysis for mixed binary quadratic programming
• Convolution and knapsack in higher dimensions
• A threshold phenomenon for the shortest lattice vector problem in the infinity norm
• Tightness of sensitivity and proximity bounds for integer linear programs

This page was built for publication: Improving proximity bounds using sparsity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225054)