On the integrality gap of binary integer programs with Gaussian data

DOI10.1007/s10107-022-01828-1OpenAlexW3112719454WikidataQ114228492 ScholiaQ114228492MaRDI QIDQ5925655

Samarth Tiwari, Daniel Dadush, Sander Borst, Sophie Huiberts

Publication date: 14 March 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-022-01828-1

zbMATH Keywords

integer programmingbranch-and-boundintegrality gap

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (1)

Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothed analysis of integer programming
• Probabilistic analysis of the generalised assignment problem
• Hyperplane sections of convex bodies in isotropic position
• Integer Programming with a Fixed Number of Variables
• The geometry of logconcave functions and sampling algorithms
• Minkowski's Convex Body Theorem and Integer Programming
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• On the complexity of integer programming
• Succinct Certificates for Almost All Subset Sum Problems
• High-Dimensional Probability
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• A Friendly Smoothed Analysis of the Simplex Method
• On the integrality gap of binary integer programs with Gaussian data

This page was built for publication: On the integrality gap of binary integer programs with Gaussian data