Improving Order with Queues

07/06/2022
by   Andreas Karrenbauer, et al.
0

Patience Sort sorts a sequence of numbers with a minimal number of queues that work according to the First-In-First-Out (FIFO) principle. More precisely, if the length of the longest descreasing subsequence of the input sequence is L, then Patience Sort uses L queues. We ask how much one can improve order with k queues, where k < L? We address this question for two measures of sortedness: number of down-steps and length of the longest descreasing subsequence. For the first measure, we give an optimal algorithm. For the second measure, we give some partial results. The research was inspired by a problem arising in car manufacturing.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset