.png){kind=icon}
.png){kind=icon}
Return
Improving order with queues
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-026-01419-2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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? 1. We give a simple algorithm, based on Patience Sort, that reduces the LDS by k-1. We also show, that the algorithm is optimal, i.e., for any L > 0 there exists a sequence of LDS L such that the LDS cannot be reduced below L- k + 1 with k queues. 2. 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. 3. 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.
Keywords:
Production
Patience Sort
Improving Order
Queues
Journal
J
IF:
1.1
Papers:
78
Citations:
0
Organization
View more organizations