On the integrality gap of binary integer programs with Gaussian data

DOI10.1007/978-3-030-73879-2_30zbMath1483.90079arXiv2012.08346OpenAlexW3160768711MaRDI QIDQ5918435

Samarth Tiwari, Sander Borst, Sophie Huiberts, Daniel Dadush

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingbranch and boundintegrality gap

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (5)

Branch-and-bound solves random binary IPs in poly\((n)\)-time ⋮ A theoretical and computational analysis of full strong-branching ⋮ On the integrality gap of binary integer programs with Gaussian data ⋮ Proximity bounds for random integer programs ⋮ On the integrality gap of binary integer programs with Gaussian data

Cites Work

• Smoothed analysis of integer programming
• Probabilistic analysis of the generalised assignment problem
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• On the complexity of integer programming
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• On the integrality gap of binary integer programs with Gaussian data
• Unnamed Item
• Unnamed Item

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