We're pleased to present Yiduo Ke on Bin packing can be solved within 1 + ε in linear time.

Read the paper: https://sci-hub.scrongyao.com/10.1007...

The bin packing problem is a well-known optimization problem in theoretical computer science, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up suitcases, loading trucks with weight capacity constraints, creating file backups, and chip design. Bin packing can be solved within 1 + ε in linear time by De la Vega and Lueker provided the first polynomial-time asymptotic approximation scheme for this problem.

Yiduo Ke is a 2024 summer research intern with Espresso AI working on scheduling algorithms to optimize Snowflake utilization. She is doing a PhD program in theoretical computer science at Northwestern University.

---

Thanks to Espresso AI (https://espresso.ai/) for making this meetup possible!