A Robust AFPTAS for Online Bin Packing with Polynomial Migration
From MaRDI portal
Publication:5241236
DOI10.1137/17M1122529zbMath1431.90096arXiv1302.4213OpenAlexW2982303827WikidataQ126856514 ScholiaQ126856514MaRDI QIDQ5241236
Kim-Manuel Klein, Klaus Jansen
Publication date: 30 October 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1302.4213
Related Items (4)
Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Online load balancing with general reassignment cost ⋮ Online minimization of the maximum starting time: migration helps ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes
Cites Work
- Unnamed Item
- Unnamed Item
- Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
- Robust algorithms for preemptive scheduling
- A robust APTAS for the classical bin packing problem
- Online algorithms. The state of the art
- Bin packing can be solved within 1+epsilon in linear time
- Using fast matrix multiplication to find basic solutions
- Algorithms for the Relaxed Online Bin-Packing Model
- Approximate Max-Min Resource Sharing for Structured Concave Optimization
- The Trim Problem
- Robust Approximation Schemes for Cube Packing
- Online Scheduling with Bounded Migration
- A Robust PTAS for Machine Covering and Packing
- Lower Bound for the Online Bin Packing Problem with Restricted Repacking
- Dynamic Bin Packing
- Sensitivity theorems in integer linear programming
- Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
- Fully-Dynamic Bin Packing with Little Repacking
- A Robust AFPTAS for Online Bin Packing with Polynomial Migration,
- Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications
- A new lower bound for classic online bin packing
This page was built for publication: A Robust AFPTAS for Online Bin Packing with Polynomial Migration
