Reconfiguration of Multisets with Applications to Bin Packing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916456477753344 |
|---|---|
| author | Kam, Jeffrey Kamali, Shahin Miller, Avery Nishimura, Naomi |
| author_facet | Kam, Jeffrey Kamali, Shahin Miller, Avery Nishimura, Naomi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05535 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconfiguration of Multisets with Applications to Bin Packing Kam, Jeffrey Kamali, Shahin Miller, Avery Nishimura, Naomi Data Structures and Algorithms Discrete Mathematics 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. |
| title | Reconfiguration of Multisets with Applications to Bin Packing |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2405.05535 |