APTAS for bin packing with general cost structures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916318783995904 |
|---|---|
| author | Jaykrishnan, G. Levin, Asaf |
| author_facet | Jaykrishnan, G. Levin, Asaf |
| contents | We consider the following generalization of the bin packing problem. We are given a set of items each of which is associated with a rational size in the interval [0,1], and a monotone non-decreasing non-negative cost function f defined over the cardinalities of the subsets of items. A feasible solution is a partition of the set of items into bins subject to the constraint that the total size of items in every bin is at most 1. Unlike bin packing, the goal function is to minimize the total cost of the bins where the cost of a bin is the value of f applied on the cardinality of the subset of items packed into the bin. We present an APTAS for this strongly NP-hard problem. We also provide a complete complexity classification of the problem with respect to the choice of f. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07677 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | APTAS for bin packing with general cost structures Jaykrishnan, G. Levin, Asaf Data Structures and Algorithms Discrete Mathematics Optimization and Control 68W25 F.2.2 We consider the following generalization of the bin packing problem. We are given a set of items each of which is associated with a rational size in the interval [0,1], and a monotone non-decreasing non-negative cost function f defined over the cardinalities of the subsets of items. A feasible solution is a partition of the set of items into bins subject to the constraint that the total size of items in every bin is at most 1. Unlike bin packing, the goal function is to minimize the total cost of the bins where the cost of a bin is the value of f applied on the cardinality of the subset of items packed into the bin. We present an APTAS for this strongly NP-hard problem. We also provide a complete complexity classification of the problem with respect to the choice of f. |
| title | APTAS for bin packing with general cost structures |
| topic | Data Structures and Algorithms Discrete Mathematics Optimization and Control 68W25 F.2.2 |
| url | https://arxiv.org/abs/2407.07677 |