On the Integrality Gap of Binary Integer Programs with Gaussian Data

Sander Borst, Daniel Dadush, Sophie Huiberts, Samarth Tiwari

Type: Preprint

Publication Date: 2020-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2012.08346

View Publication

Locations

arXiv (Cornell University) - View
Data Archiving and Networked Services (DANS) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	On the integrality gap of binary integer programs with Gaussian data	2021	Sander Borst Daniel Dadush Sophie Huiberts Samarth Tiwari
+	Integrality Gaps for Random Integer Programs via Discrepancy	2022	Sander Borst Daniel Dadush Dan Mikulincer
+ PDF Chat	On the Integrality Gap of Binary Integer Programs with Gaussian Data	2021	Sander Borst Daniel Dadush Sophie Huiberts Samarth Tiwari
+ PDF Chat	On the integrality gap of binary integer programs with Gaussian data	2022	Sander Borst Daniel Dadush Sophie Huiberts Samarth Tiwari
+ PDF Chat	Integrality Gaps for Random Integer Programs via Discrepancy	2023	Sander Borst Daniel Dadush Dan Mikulincer
+ PDF Chat	Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model	2022	Yingjie Fei Yudong Chen
+ PDF Chat	$$\ell _1$$-sparsity Approximation Bounds for Packing Integer Programs	2019	Chandra Chekuri Kent Quanrud Manuel R. Torres
+ PDF Chat	$$\ell _1$$-Sparsity approximation bounds for packing integer programs	2020	Chandra Chekuri Kent Quanrud Manuel R. Torres
+	Branch-and-Bound Solves Random Binary Packing IPs in Polytime	2020	Santanu S. Dey Yatharth Dubey Marco Molinaro
+	Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Model	2018	Yingjie Fei Yudong Chen
+ PDF Chat	Robust Secretary and Prophet Algorithms for Packing Integer Programs	2022	C. J. Argue Anupam Gupta Marco Molinaro Sahil Singla
+	Branch-and-Bound Solves Random Binary Packing IPs in Polytime	2021	Yatharth Dubey Santanu S. Dey Marco Molinaro
+	Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs	2021	Khaled Elbassioni Kazuhisa Makino
+ PDF Chat	Exact Semidefinite Programming Bounds for Packing Problems	2021	Maria Dostert David de Laat Philippe Moustrou
+	Lower Bounds on the Size of General Branch-and-Bound Trees.	2021	Santanu S. Dey Yatharth Dubey Marco Molinaro
+	Hidden Integrality of SDP Relaxation for Sub-Gaussian Mixture Models	2018	Yingjie Fei Yudong Chen
+ PDF Chat	Extended Formulation Lower Bounds for Refuting Random CSPs	2019	Jonah Brown-Cohen Prasad Raghavendra
+	$\ell_p$-Regression in the Arbitrary Partition Model of Communication	2023	Yi Li Honghao Lin David P. Woodruff
+ PDF Chat	Polynomial Integrality Gap of Flow LP for Directed Steiner Tree	2022	Shi Li Bundit Laekhanukit
+ PDF Chat	Algorithms to Approximate Column-Sparse Packing Problems	2018	Brian Brubach Karthik Abinav Sankararaman Aravind Srinivasan Pan Xu

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors