EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Improving order with queues

Andreas Karrenbauer, Kurt Mehlhorn, Pranabendu Misra, Paolo Luigi Rinaldi, Anna Twelsiek, Alireza Haqi, Siavash Rahimi Shateranloo

Journal of Combinatorial Optimization · 2026-04 · 51 (3)

DOI: 10.1007/s10878-026-01419-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Combinatorial Optimization, online erschienen am 13.04.2026. Verfasst von Andreas Karrenbauer und 6 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Regional Development Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a sequence of n numbers and k parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that k queues suffice to sort the sequence if the Longest Decreasing Subsequence (LDS) of the input sequence is at most k . But, what if the number of queues is too small for sorting completely? We give a simple algorithm, based on Patience Sort, that reduces the LDS by $$k - 1$$ k - 1 . We also show, that the algorithm is optimal, i.e., for any $$L > 0$$ L > 0 there exists a sequence of LDS L such that the LDS cannot be reduced below $$L - k + 1$$ L - k + 1 with k queues. Merging two sorted queues is at the core of Merge Sort. In contrast, two sequences of LDS two cannot always be merged into a sequence of LDS two. We characterize when it is possible and give an algorithm to decide whether it is possible. Merging into a sequence of LDS three is always possible. A down-step in a sequence is an item immediately followed by a smaller item. We give an optimal algorithm for reducing the number of down-steps. The algorithm is online. Our research was inspired by an application in car manufacturing.

Förderung

  • European Regional Development Fund

Zitieren

APA

Karrenbauer, A., Mehlhorn, K., Misra, P., Rinaldi, P. L., Twelsiek, A., Haqi, A., & Shateranloo, S. R. (2026). Improving order with queues. Journal of Combinatorial Optimization, 51(3). https://doi.org/10.1007/s10878-026-01419-2

Vancouver

Karrenbauer A, Mehlhorn K, Misra P, Rinaldi PL, Twelsiek A, Haqi A, et al. Improving order with queues. Journal of Combinatorial Optimization. 2026;51(3). doi:10.1007/s10878-026-01419-2

BibTeX
@article{Karrenbauer2026,
  author = {Karrenbauer, Andreas and Mehlhorn, Kurt and Misra, Pranabendu and Rinaldi, Paolo Luigi and Twelsiek, Anna and Haqi, Alireza and Shateranloo, Siavash Rahimi},
  title = {Improving order with queues},
  journal = {Journal of Combinatorial Optimization},
  year = {2026},
  volume = {51},
  number = {3},
  doi = {10.1007/s10878-026-01419-2}
}
Kostenlos starten →