Unbounded bin-packing gaps and the modified integer round-up conjecture at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

Unbounded bin-packing gaps and the modified integer round-up conjecture

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	algorithms, speed	Levels:	1
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.5 out of 5 (4,515 votes)

>>> How to Play <<<

Bin packing and unbounded configuration-LP gaps. Disproves the modified integer round-up conjecture of Scheithauer and Terno: the integral bin-packing optimum can exceed its configuration linear-programming value by an arbitrarily large additive constant. Approximating the optimum within any fixed additive constant is also NP-hard, even when every item exceeds 1/6 and each bin holds at most five items.

>>> Level Select <<<

LEVEL 1 Additive hardness and unbounded configuration gaps in bin packing

released 2026-09-24 | 3 theorems · 10 lemmas · 16 proofs · 12,530 words | PLAY LEVEL 1 » (pdf)

We disprove the Modified Integer Round-Up Conjecture for bin packing by constructing instances with arbitrarily large additive gaps between the configuration-LP value and the integral optimum. We also prove that, for every fixed nonnegative integer c, distinguishing instances that fit in B bins from those requiring more than $B+c$ bins is NP-hard. Both results hold with rational item sizes greater than 1/6, so each bin contains at most five items.

More Theoretical computer science Games!
The approximation threshold for metric $k$-median	Exponential semidefinite complexity of perfect matching	The asymptotic Gotsman–Linial conjecture	A factor-two approximation for shortest common superstring
Exponential state costs for two-way automata	Fourier transforms below $n\log n$ HOT!	Polynomial mixing of graph switches with prescribed degrees	A counterexample to the quadratic sensitivity conjecture

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600