Reconfiguration of Multisets with Applications to Bin Packing
Abstract
We use the reconfiguration framework to analyze problems that involve the rearrangement of items among groups. In various applications, a group of items could correspond to the files or jobs assigned to a particular machine, and the goal of rearrangement could be improving efficiency or increasing locality. To cover problems arising in a wide range of application areas, we define the general Repacking problem as the rearrangement of multisets of multisets. We present hardness results for the general case and algorithms for various classes of instances that arise in real-life scenarios. By limiting the total size of items in each multiset, our results can be viewed as an offline approach to Bin Packing, in which each bin is represented as a multiset. In addition to providing the first results on reconfiguration of multisets, our contributions open up several research avenues: the interplay between reconfiguration and online algorithms and parallel algorithms; the use of the tools of linear programming in reconfiguration; and, in the longer term, a focus on extra resources in reconfiguration.
- Publication:
-
arXiv e-prints
- Pub Date:
- May 2024
- DOI:
- arXiv:
- arXiv:2405.05535
- Bibcode:
- 2024arXiv240505535K
- Keywords:
-
- Computer Science - Data Structures and Algorithms;
- Computer Science - Discrete Mathematics
- E-Print:
- A preliminary version of this paper appeared in the proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024)