Feasibility criteria for high-multiplicity partitioning problems
From MaRDI portal
Publication:2069802
DOI10.1016/J.JPAA.2021.106937zbMATH Open1483.90143arXiv1909.02155OpenAlexW3217091519MaRDI QIDQ2069802FDOQ2069802
Authors: Claudiu Raicu 
Publication date: 21 January 2022
Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1909.02155
Recommendations
Cites Work
- Bin packing can be solved within 1+epsilon in linear time
- Polynomiality for bin packing with a constant number of item types
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
- Title not available (Why is that?)
- The \(k\)-partitioning problem
- Title not available (Why is that?)
- An asymptotically exact algorithm for the high-multiplicity bin packing problem
- Regularity of \(\mathfrak{S}_n\)-invariant monomial ideals
- Combinatorial optimization. Theory and algorithms
Uses Software
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)
