Improving Order with Queues
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912589163790336 |
|---|---|
| author | Karrenbauer, Andreas Mehlhorn, Kurt Misra, Pranabendu Rinaldi, Paolo Luigi Twelsiek, Anna Haqi, Alireza Shateranloo, Siavash Rahimi |
| author_facet | Karrenbauer, Andreas Mehlhorn, Kurt Misra, Pranabendu Rinaldi, Paolo Luigi Twelsiek, Anna Haqi, Alireza Shateranloo, Siavash Rahimi |
| contents | 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$. 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.
- 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_02476 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Improving Order with Queues Karrenbauer, Andreas Mehlhorn, Kurt Misra, Pranabendu Rinaldi, Paolo Luigi Twelsiek, Anna Haqi, Alireza Shateranloo, Siavash Rahimi Data Structures and Algorithms 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$. 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. - 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. |
| title | Improving Order with Queues |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2207.02476 |