Feasibility criteria for high-multiplicity partitioning problems

DOI10.1016/J.JPAA.2021.106937MaRDI QIDQ2069802zbMATH OpenOpenAlexFDO

Authors Claudiu Raicu

Publication date 21 January 2022

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

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

zbMATH Keywords

bin packingpartitioning problemfeasibility criteria

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Extremal combinatorics (05D99)

Abstract: For fixed weights w_1,...,w_n, and for d>0, we let B denote a collection of d*n balls, with d balls of weight w_i for each i=1,...,n. We consider the problem of assigning the balls to n bins with capacities C_1,...,C_n, in such a way that each bin is assigned d balls, without exceeding its capacity. When d>>0, we give sufficient criteria for the feasibility of this problem, which coincide up to explicit constants with the natural set of necessary conditions. Furthermore, we show that our constants are optimal when the weights w_i are distinct. The feasibility criteria that we present here are used elsewhere (in commutative algebra) to study the asymptotic behavior of the Castelnuovo-Mumford regularity of symmetric monomial ideals.

Recommendations

• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• scientific article; zbMATH DE number 4168692
• Multiply balanced \(k\)-partitioning
• scientific article; zbMATH DE number 4195959
• The \(k\)-partitioning problem

Cites work

• scientific article; zbMATH DE number 5504153 (Why is no real title available?)
• scientific article; zbMATH DE number 6472627 (Why is no real title available?)
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Bin packing can be solved within 1+epsilon in linear time
• Combinatorial optimization. Theory and algorithms
• Polynomiality for bin packing with a constant number of item types
• Regularity of \(\mathfrak{S}_n\)-invariant monomial ideals
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• The \(k\)-partitioning problem

Describes a project that uses

Uses Software

• Macaulay2

This page was built for publication: Feasibility criteria for high-multiplicity partitioning problems

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