On bin packing with clustering and bin packing with delays
From MaRDI portal
Publication:2234744
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6678949 (Why is no real title available?)
- scientific article; zbMATH DE number 563208 (Why is no real title available?)
- A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
- A match in time saves nine: deterministic online matching with delays
- A new and improved algorithm for online bin packing
- A simple on-line bin-packing algorithm
- Batched bin packing
- Batched bin packing revisited
- Bin packing can be solved within 1+epsilon in linear time
- Competitive snoopy caching
- Dynamic TCP Acknowledgment: Penalizing Long Delays
- Dynamic TCP acknowledgment and other stories about \(e/(e-1)\)
- Improved Space for Bounded-Space, On-Line Bin-Packing
- Lower bound for 3-batched bin packing
- More on batched bin packing
- On Bin Packing with Conflicts
- On-line analysis of the TCP acknowledgment delay problem
- Online bin packing with delay and holding costs
- Online matching: haste makes waste!
- Online service with delay
- Optimal analysis of best fit bin packing
- Repacking helps in bounded space on-line bin-packing
- The optimal absolute ratio for online bin packing
Cited in
(5)- Approximation algorithms for the generalized incremental knapsack problem
- Open-end bin packing: new and old analysis approaches
- Several methods of analysis for cardinality constrained bin packing
- Several methods of analysis for cardinality constrained bin packing
- The bin covering with delivery problem, extended investigations for the online case
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)
