Yiduo Ke on Bin packing can be solved within 1 + ε in linear time
Details
Thank you to Espresso AI for hosting!
We're pleased to present Yiduo Ke on Bin packing can be solved within 1 + ε in linear time. (Paper Link).
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.
---
🚔 Reminder: Papers We Love has a code of conduct. Breaching the CoC is grounds to be ejected from the meetup at the organizers' discretion.
📹 The event will be recorded and made available 1-2 weeks afterwards.
💬 Join us on the Papers We Love Discord - https://discord.gg/6gupsBg4qp
Venue:
Espresso AI
Level 4
25 Kent Ave Brooklyn, NY 11249
Yiduo Ke on Bin packing can be solved within 1 + ε in linear time