|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
18 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Algorithms for the Pagination Problem, a Bin Packing with Overlapping Items | | Aristide Grange
; Imed Kacem
; Sébastien Martin
; | | Date: |
2 May 2016 | | Abstract: | We introduce the strongly NP-complete pagination problem, an extension of BIN
PACKING where packing together two items may make them occupy less volume than
the sum of their individual sizes. To achieve this property, an item is defined
as a finite set of symbols from a given alphabet: while, in BIN PACKING, any
two such sets would be disjoint, in PAGINATION, they can share zero, one or
more symbols. After formulating the problem as an integer linear program, we
try to approximate its solutions with several families of algorithms: from
straightforward adaptations of classical BIN PACKING heuristics, to dedicated
algorithms (greedy and non-greedy), to standard and grouping genetic
algorithms. All of them are studied first theoretically, then experimentally on
an extensive random test set. Based upon these data, we propose a predictive
measure of the difficulty of a given instance, and finally recommend which
algorithm should be used in which case, depending on either time constraints or
quality requirements. | | Source: | arXiv, 1605.0558 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER