When piling a set of items in a single stack, one often does not pay attention to the order. Real-life experience suggests that, whenever a specific item is suddenly requested, we need to dig very deep into the stack to extract it.In this paper we investigate stack reordering strategies aiming at minimizing the number of "pop" and "push" operations. In particular we focus on three versions of the problem in which reordering can take place in different phases: when unloading the stack, when loading it or in both phases.We show that the first two variants can be solved in linear time, while for the third one we devise a dynamic programming method with quadratic complexity.

The stack loading and unloading problem / F., Malucelli; S., Pallottino; Pretolani, Daniele. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 156:(2008), pp. 3248-3266. [10.1016/j.dam.2008.05.020]

The stack loading and unloading problem

PRETOLANI, Daniele
2008

Abstract

When piling a set of items in a single stack, one often does not pay attention to the order. Real-life experience suggests that, whenever a specific item is suddenly requested, we need to dig very deep into the stack to extract it.In this paper we investigate stack reordering strategies aiming at minimizing the number of "pop" and "push" operations. In particular we focus on three versions of the problem in which reordering can take place in different phases: when unloading the stack, when loading it or in both phases.We show that the first two variants can be solved in linear time, while for the third one we devise a dynamic programming method with quadratic complexity.
156
3248
3266
The stack loading and unloading problem / F., Malucelli; S., Pallottino; Pretolani, Daniele. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 156:(2008), pp. 3248-3266. [10.1016/j.dam.2008.05.020]
F., Malucelli; S., Pallottino; Pretolani, Daniele
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/612728
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact