<p>I know that it has been conjectured that the Gilmore–Gomory LP for 1-D BP (also known as configuration LP) has
Modified Integer Roundup Property, i.e., Opt ≤ ⌈Opt_f⌉ + 1. However, I could not find the best-known lower bound for the integrality gap of the latter LP. Can anyone refer me to such a result?</p>
<p>Thanks in advance.</p>

CC BY-SA 4.0
2022-09-20T23:37:05.133Z
See this paper of Hobert and Rothvoss. https://arxiv.org/abs/1503.08796
Chandra Chekuri
CC BY-SA 4.0
2022-09-28T15:01:00.000Z
Thank you very much!
John
<linear-programming><packing><integrality-gap>
What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?
John
# What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

(Asked by: username_0 on 2022-09-20)

I know that it has been conjectured that the Gilmore–Gomory LP for 1-D BP (also known as configuration LP) has
Modified Integer Roundup Property, i.e., Opt ≤ ⌈Opt\_f⌉ + 1. However, I could not find the best-known lower bound for the integrality gap of the latter LP. Can anyone refer me to such a result?

Thanks in advance.

**Tags:** linear-programming, packing, integrality-gap
> **Comments:**
> **username_1**: See this paper of Hobert and Rothvoss. https://arxiv.org/abs/1503.08796  
> **username_0**: Thank you very much!  

---

## 0 answers

