Timeline for Influence of Vertex Weights on Performance of Polyhedral TSP Algorithms
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Jan 4, 2018 at 19:17 | comment | added | Manfred Weis | So the answer to my question would be "yes" in the sense, that adding/subtracting vertex weights influences the execution of polyhedral TSP algorithms, even if the restriction on optimal tour length isn't tightened? | |
| Jan 4, 2018 at 18:02 | comment | added | John Gunnar Carlsson | I'm not sure I fully understand your question, but the one-tree relaxation definitely involves iteratively changing the edge weights. | |
| Jan 4, 2018 at 17:52 | comment | added | Manfred Weis | @JohnGunnarCarlsson that's exactly the case, but AFAIK only the numerical value of the upper bound is exploited by adding it as a constraint on the length of optimal tour; the edge-weights of the problem instance are however not modified - please correct me, if I'm wrong. What my questions aims at, is a bit different, namely what would happen, if we don't add the improved length-constraint and instead modify only the edge-weights of the problem instance. | |
| Jan 4, 2018 at 17:22 | comment | added | John Gunnar Carlsson | This sounds exactly like the One-tree relaxation: www2.imm.dtu.dk/courses/02713/NewLectures/bbtsp4.pdf | |
| Jan 4, 2018 at 9:37 | history | asked | Manfred Weis | CC BY-SA 3.0 |