Improved analysis of two algorithms for min-weighted sum bin packing

DOI10.1007/978-3-031-34347-6_29MaRDI QIDQ6182919zbMATH OpenOpenAlexFDO

Authors Guillaume Sagnol

Publication date 22 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.02498

zbMATH Keywords

approximation algorithmsbatch schedulingbin packing

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: We study the Min-Weighted Sum Bin Packing problem, a variant of the classical Bin Packing problem in which items have a weight, and each item induces a cost equal to its weight multiplied by the index of the bin in which it is packed. This is in fact equivalent to a batch scheduling problem that arises in many fields of applications such as appointment scheduling or warehouse logistics. We give improved lower and upper bounds on the approximation ratio of two simple algorithms for this problem. In particular, we show that the knapsack-batching algorithm, which iteratively solves knapsack problems over the set of remaining items to pack the maximal weight in the current bin, has an approximation ratio of at most 17/10.

Cites work

• A survey of scheduling with parallel batch (p-batch) processing
• An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule
• Approximating min sum set cover
• Batch scheduling of nonidentical job sizes with minsum criteria
• scientific article; zbMATH DE number 6678949 (Why is no real title available?)
• scientific article; zbMATH DE number 3557207 (Why is no real title available?)
• Min-sum bin packing
• Minimum Weighted Sum Bin Packing
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The Batch Loading and Scheduling Problem

Cited in

(4)

• Deep performance analysis of refined harmonic bin packing algorithm
• Analysis of a Hybrid Algorithm for Packing Unequal Bins
• Surgery scheduling in flexible operating rooms by using a convex surrogate model of second-stage costs
• Algorithmic analysis of priority-based bin packing

This page was built for publication: Improved analysis of two algorithms for min-weighted sum bin packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182919)