On bin packing with clustering and bin packing with delays
From MaRDI portal
Publication:2234744
DOI10.1016/J.DISOPT.2021.100647zbMATH Open1506.90222arXiv1908.06727OpenAlexW3167861864MaRDI QIDQ2234744FDOQ2234744
Authors: Leah Epstein 
Publication date: 19 October 2021
Published in: Discrete Optimization (Search for Journal in Brave)
Abstract: We continue the study of two recently introduced bin packing type problems, called bin packing with clustering, and online bin packing with delays. A bin packing input consists of items of sizes not larger than 1, and the goal is to partition or pack them into bins, where the total size of items of every valid bin cannot exceed 1. In bin packing with clustering, items also have colors associated with them. A globally optimal solution can combine items of different colors in bins, while a clustered solution can only pack monochromatic bins. The goal is to compare a globally optimal solution to an optimal clustered solution, under certain constraints on the coloring provided with the input. We show close bounds on the worst-case ratio between these two costs, called "the price of clustering", improving and simplifying previous results. Specifically, we show that the price of clustering does not exceed 1.93667, improving over the previous upper bound of 1.951, and that it is at least 1.93558, improving over the previous lower bound of 1.93344. In online bin packing with delays, items are presented over time. Items may wait to be packed, and an algorithm can create a new bin at any time, packing a subset of already existing unpacked items into it, under the condition that the bin is valid. A created bin cannot be used again in the future, and all items have to be packed into bins eventually. The objective is to minimize the number of used bins plus the sum of waiting costs of all items, called delays. We build on previous work and modify a simple phase-based algorithm. We combine the modification with a careful analysis to improve the previously known competitive ratio from 3.951 to below 3.1551.
Full work available at URL: https://arxiv.org/abs/1908.06727
Recommendations
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)
Cites Work
- Bin packing can be solved within 1+epsilon in linear time
- Repacking helps in bounded space on-line bin-packing
- On Bin Packing with Conflicts
- A simple on-line bin-packing algorithm
- Title not available (Why is that?)
- Competitive snoopy caching
- Online bin packing with delay and holding costs
- Improved Space for Bounded-Space, On-Line Bin-Packing
- Batched bin packing
- Title not available (Why is that?)
- Optimal analysis of best fit bin packing
- On-line analysis of the TCP acknowledgment delay problem
- Dynamic TCP Acknowledgment: Penalizing Long Delays
- Batched bin packing revisited
- A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
- Dynamic TCP acknowledgment and other stories about \(e/(e-1)\)
- The optimal absolute ratio for online bin packing
- Title not available (Why is that?)
- Online matching: haste makes waste!
- A match in time saves nine: deterministic online matching with delays
- Online service with delay
- Lower bound for 3-batched bin packing
- More on batched bin packing
Cited In (5)
- Several methods of analysis for cardinality constrained bin packing
- Several methods of analysis for cardinality constrained bin packing
- Open-end bin packing: new and old analysis approaches
- The bin covering with delivery problem, extended investigations for the online case
- Approximation algorithms for the generalized incremental knapsack problem
This page was built for publication: On bin packing with clustering and bin packing with delays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234744)
