Timeline for Given $N$ integers on a circle, how to choose them in pairs to obtain minimum sum?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 7, 2019 at 13:28 | history | edited | Manfred Weis | CC BY-SA 4.0 |
provided and improved heuristic that yields correct results for the sample instance
|
| Jul 7, 2019 at 8:07 | comment | added | user142757 | @ManfredWeis Can you remove the answer since it is from a contest . | |
| Jul 6, 2019 at 22:14 | comment | added | Gerhard Paseman | There is a straightforward cubic algorithm with quadratic space that solves this problem. It may be possible to optimize on both space and time. However, I imagine this Is an exam question or contest problem. I hope that the original poster will mention where they found the problem. Gerhard "Isn't Feeling Dynamic At Present" Paseman, 2019.07.06. | |
| Jul 6, 2019 at 13:38 | history | edited | Manfred Weis | CC BY-SA 4.0 |
corrected the calculation of the optimal sequence
|
| Jul 6, 2019 at 13:23 | history | edited | Manfred Weis | CC BY-SA 4.0 |
demonstrated the failure of the heuristic with the sequence provided by @Shrijana
|
| Jul 6, 2019 at 12:39 | comment | added | Manfred Weis | @Shrijana I do not yet have an answer, but I will try find one; as I said: it is an interesting problem and maybe it only needs a simple key idea. Hopefully your question receives broader attention. | |
| Jul 6, 2019 at 11:57 | comment | added | user142755 | I do not know but i think it has answer .Do you have some idea how to solve the problem ?I am trying it from long time | |
| Jul 6, 2019 at 11:52 | history | edited | Manfred Weis | CC BY-SA 4.0 |
replaced "algorithm" with "heuristic"
|
| Jul 6, 2019 at 11:51 | comment | added | Manfred Weis | @Shrijana I will replace "algorithm" by "heuristic" but leave the answer to illustrate, together with your counter example, that there isn't an easy answer. | |
| Jul 6, 2019 at 11:32 | comment | added | user142755 | your algorithm does not works always .For example consider 9,4,2,3,2,9 . In this case if 2,3 is chosen in first iteration instead for 3,2 final answer is wrong . | |
| Jul 6, 2019 at 11:03 | history | answered | Manfred Weis | CC BY-SA 4.0 |