Bin Packing Can Be Solved Within 1 + ε in Linear Time - Lecture

Explore a conference talk by Yiduo Ke on the groundbreaking algorithm for solving the bin packing problem within 1 + ε in linear time. Delve into this well-known optimization challenge in theoretical computer science, where items of varying sizes must be efficiently packed into a limited number of fixed-capacity bins. Discover the polynomial-time asymptotic approximation scheme developed by De la Vega and Lueker, which revolutionized the approach to this problem. Learn about the wide-ranging applications of bin packing, from practical scenarios like filling suitcases and loading trucks to technological uses in file backups and chip design. Gain insights from Yiduo Ke, a PhD candidate in theoretical computer science at Northwestern University and summer research intern at Espresso AI, as she presents this complex topic in an accessible manner.

Yiduo Ke on Bin packing can be solved within 1 + ε in linear time [PWL NYC]