Timeline for Is there an algorithm to merge $d$ chains into $\left\lceil\frac{d}{k}\right\rceil$ chains?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2021 at 2:33 | comment | added | Sirawit 'Plum' P. | That sounds right. I'll inform this to my colleague and will investigate this more. Thanks. | |
| Jun 9, 2021 at 0:22 | comment | added | user1020406 | I wrote a small program to search for counterexamples for k = 2, and the shortest it found is (1 8 3 9 5 10 7 2 4 6). The longest increasing sub sequence has length 4. It seems that it's not possible to reduce that length to 2 by a single application of the operation from your question. Of course, my program can be buggy, so I'd appreciate if you could verify this. | |
| Jun 8, 2021 at 16:04 | comment | added | Sirawit 'Plum' P. | A colleague of mine found a counterexample (13 17 12 14 3 19 16 11 1 8 9 10 5 18 4 6 15 7 0 2) for k=2. Here, by always extending the first possible subsequence, we end up with 5 chains: (13 12 3 1 0, 17 14 11 8 5 4 2, 19 16 9 6, 10 7, 18 15). Let's pack the first, third, and fifth chains together to be (13 12 3 19 16 1 9 18 6 15 0) and then pack the second and fourth chains to (17 14 11 8 10 5 4 7 2). Keep in mind that here we want to merge the first with the second, and merge the third with the fourth, and leave the fifth as it was. It fails during "mergesort" at (17 14 13 12 11 8 *). | |
| Jun 8, 2021 at 12:56 | comment | added | user1020406 | How about decomposing the original sequence into decreasing subsequences in a greedy way (you always extend the first possible subsequence)? For example, (5 6 1 2 4 3 0) decomposes into (5 1, 6 2 0, 4 3). You then distribute these subsequnces into your k=2 queues in any "balanced" way without splitting any of those subsequences, for example 5 6 1 2 4 3 0 -> (5 6 1 2 0, 4 3) or (5 1 4 3, 6 2 0). Then you "mergesort" the k=2 queues into (5 6 4 3 1 2 0) or (6 5 2 1 4 3 0). After one more iteration you get (6 5 4 3 2 1 0). I think this should work, are there any counterexamples? | |
| Jun 7, 2021 at 16:50 | review | First posts | |||
| Jun 7, 2021 at 17:17 | |||||
| Jun 7, 2021 at 16:49 | history | asked | Sirawit 'Plum' P. | CC BY-SA 4.0 |