{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T09:13:27Z","timestamp":1778058807587,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"vor","delay-in-days":12,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a sequence of\n                    <jats:italic>n<\/jats:italic>\n                    numbers and\n                    <jats:italic>k<\/jats:italic>\n                    parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that\n                    <jats:italic>k<\/jats:italic>\n                    queues suffice to sort the sequence if the\n                    <jats:italic>Longest Decreasing Subsequence (LDS)<\/jats:italic>\n                    of the input sequence is at most\n                    <jats:italic>k<\/jats:italic>\n                    . But, what if the number of queues is too small for sorting completely?\n                    <jats:list list-type=\"order\">\n                      <jats:list-item>\n                        <jats:p>\n                          We give a simple algorithm, based on Patience Sort, that reduces the LDS by\n                          <jats:inline-formula>\n                            <jats:alternatives>\n                              <jats:tex-math>$$k - 1$$<\/jats:tex-math>\n                              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                                <mml:mrow>\n                                  <mml:mi>k<\/mml:mi>\n                                  <mml:mo>-<\/mml:mo>\n                                  <mml:mn>1<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:math>\n                            <\/jats:alternatives>\n                          <\/jats:inline-formula>\n                          . We also show, that the algorithm is optimal, i.e., for any\n                          <jats:inline-formula>\n                            <jats:alternatives>\n                              <jats:tex-math>$$L &gt; 0$$<\/jats:tex-math>\n                              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                                <mml:mrow>\n                                  <mml:mi>L<\/mml:mi>\n                                  <mml:mo>&gt;<\/mml:mo>\n                                  <mml:mn>0<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:math>\n                            <\/jats:alternatives>\n                          <\/jats:inline-formula>\n                          there exists a sequence of LDS\n                          <jats:italic>L<\/jats:italic>\n                          such that the LDS cannot be reduced below\n                          <jats:inline-formula>\n                            <jats:alternatives>\n                              <jats:tex-math>$$L - k + 1$$<\/jats:tex-math>\n                              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                                <mml:mrow>\n                                  <mml:mi>L<\/mml:mi>\n                                  <mml:mo>-<\/mml:mo>\n                                  <mml:mi>k<\/mml:mi>\n                                  <mml:mo>+<\/mml:mo>\n                                  <mml:mn>1<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:math>\n                            <\/jats:alternatives>\n                          <\/jats:inline-formula>\n                          with\n                          <jats:italic>k<\/jats:italic>\n                          queues.\n                        <\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>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.<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>\n                          A\n                          <jats:italic>down-step<\/jats:italic>\n                          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.\n                        <\/jats:p>\n                      <\/jats:list-item>\n                    <\/jats:list>\n                    Our research was inspired by an application in car manufacturing.\n                  <\/jats:p>","DOI":"10.1007\/s10878-026-01419-2","type":"journal-article","created":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T16:05:47Z","timestamp":1776096347000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improving order with queues"],"prefix":"10.1007","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6129-3220","authenticated-orcid":false,"given":"Andreas","family":"Karrenbauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4020-4334","authenticated-orcid":false,"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7086-5590","authenticated-orcid":false,"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1963-4516","authenticated-orcid":false,"given":"Paolo Luigi","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Twelsiek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7087-3798","authenticated-orcid":false,"given":"Alireza","family":"Haqi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siavash","family":"Rahimi Shateranloo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,13]]},"reference":[{"issue":"4","key":"1419_CR1","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D Aldous","year":"1999","unstructured":"Aldous D, Diaconis P (1999) Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull Am Math Soc 36(4):413\u2013432","journal-title":"Bull Am Math Soc"},{"key":"1419_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall B, Plass M, Tarjan R (1979) A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf Process Lett 8:121\u2013123","journal-title":"Inf Process Lett"},{"issue":"3","key":"1419_CR3","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1016\/j.ejor.2019.08.005","volume":"280","author":"S Boge","year":"2020","unstructured":"Boge S, Knust S (2020) The parallel stack loading problem minimizing the number of reshuffles in the retrieval stage. Eur J Oper Res 280(3):940\u2013952. https:\/\/doi.org\/10.1016\/j.ejor.2019.08.005","journal-title":"Eur J Oper Res"},{"issue":"11","key":"1419_CR4","doi-asserted-by":"publisher","first-page":"2764","DOI":"10.1109\/TPDS.2021.3076534","volume":"32","author":"M Boroujeni","year":"2021","unstructured":"Boroujeni M, Ghodsi M, Seddighin S (2021) Improved MPC algorithms for edit distance and Ulam distance. IEEE Trans Parallel Distrib Syst 32(11):2764\u20132776. https:\/\/doi.org\/10.1109\/TPDS.2021.3076534","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"1419_CR5","doi-asserted-by":"publisher","unstructured":"Boysen N, Emde S (2016) The parallel stack loading problem to minimize blockages. Eur J Oper Res 249(2):618\u2013627. https:\/\/doi.org\/10.1016\/j.ejor.2015.09.033. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0377221715008759","DOI":"10.1016\/j.ejor.2015.09.033"},{"key":"1419_CR6","doi-asserted-by":"publisher","unstructured":"Chandramouli B, Goldstein J (2014) Patience is a virtue: Revisiting merge and sort on modern processors. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, SIGMOD \u201914, p 731\u2013742,https:\/\/doi.org\/10.1145\/2588555.2593662,","DOI":"10.1145\/2588555.2593662"},{"key":"1419_CR7","unstructured":"Cormen TH, Leiserson CE, Rivest RL, et\u00a0al (2022) Introduction to algorithms. MIT press"},{"key":"1419_CR8","doi-asserted-by":"crossref","unstructured":"Even S, Itai A (1971) Queues, stacks and graphs. In: Theory of machines and computations. Elsevier, p 71\u201386","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"key":"1419_CR9","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1057\/palgrave.jors.2602361","volume":"59","author":"C Gagn\u00e9","year":"2008","unstructured":"Gagn\u00e9 C, Gravel M, Morin S et al (2008) Impact of the pheromone trail on the performance of ACO algorithms for solving the car-sequencing problem. Journal of the Operational Research Society 59:1077\u20131090","journal-title":"Journal of the Operational Research Society"},{"key":"1419_CR10","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Elsevier"},{"key":"1419_CR11","unstructured":"Gopalan P, Jayram T, Krauthgamer R, et\u00a0al (2007) Estimating the sortedness of a data stream. In: SODA"},{"key":"1419_CR12","unstructured":"Karrenbauer A, Kuhn B, Mehlhorn K, et\u00a0al (2025) Optimizing car resequencing on mixed-model assembly lines: Algorithm development and deployment. https:\/\/arxiv.org\/abs\/2507.17422, arXiv:2507.17422"},{"key":"1419_CR13","unstructured":"Knuth DE (1968) The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley"},{"key":"1419_CR14","doi-asserted-by":"crossref","unstructured":"Mallows CL (1963) Patience sorting SIAM review 5(4):375","DOI":"10.1137\/1005107"},{"key":"1419_CR15","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1016\/j.ejor.2008.03.033","volume":"197","author":"S Morin","year":"2009","unstructured":"Morin S, Gagn\u00e9 C, Gravel M (2009) Ant colony optimization with a specialized pheromone trail for the car-sequencing problem. Eur J Oper Res 197:1185\u20131191","journal-title":"Eur J Oper Res"},{"key":"1419_CR16","doi-asserted-by":"publisher","unstructured":"Pratt VR (1973) Computing permutations with double-ended queues, parallel stacks and parallel queues. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, New York, NY, USA, STOC \u201973, p 268\u2013277, https:\/\/doi.org\/10.1145\/800125.804058,","DOI":"10.1145\/800125.804058"},{"key":"1419_CR17","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C Schensted","year":"1961","unstructured":"Schensted C (1961) Longest increasing and decreasing subsequences. Can J Math 13:179\u2013191","journal-title":"Can J Math"},{"issue":"2","key":"1419_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"R Tarjan","year":"1972","unstructured":"Tarjan R (1972) Sorting using networks of queues and stacks. Journal of the ACM (JACM) 19(2):341\u2013346","journal-title":"Journal of the ACM (JACM)"},{"key":"1419_CR19","unstructured":"Twelsiek AK (2021) Production planning of mixed-model assembly lines at the Ford Saarlouis plant. Master\u2019s thesis, Universit\u00e4t des Saarlandes"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01419-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01419-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01419-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T08:20:40Z","timestamp":1778055640000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01419-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1419"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01419-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4]]},"assertion":[{"value":"20 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"39"}}