Timeline for Heuristics for lightweighted "cubic" spanning trees
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| yesterday | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 13 at 20:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 15 at 19:08 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 17, 2023 at 19:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 19, 2023 at 18:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 21, 2023 at 17:08 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 22, 2022 at 17:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 24, 2022 at 17:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 26, 2022 at 17:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 27, 2021 at 16:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 27, 2021 at 15:27 | answer | added | Manfred Weis | timeline score: 0 | |
| Nov 27, 2021 at 14:44 | comment | added | Manfred Weis | Of course the inapproximability for $\lbrace 1, 2\rbrace$ edge weights is plausible, but there are also situations where the edgeweights allow for good approximation ratios, most prominently the planar Euclidean TSP and I am looking for heursitics for the problem stated as the above question that work well in specific situations. | |
| Nov 22, 2021 at 20:30 | comment | added | Manuel Lafond | I'd conjecture that no good approx guarantee can be achieved. In an unweighted graph, deciding if there is a $\{1, 2\}$-spanning tree is NP-hard (that's the Hamiltonian path problem). This is used to show that finding a min-weight $\{1, 2\}$-spanning tree in a complete graph, i.e. TSP, can't be approximated by essentially any ratio (by replacing non-edges with edges of huge weight). The same ideas should apply to $\{1, 3\}$-spanning trees. It's probably NP-hard to find one in unweighted graphs, making the weighted complete version inapproximable. Requires proof though. | |
| Nov 22, 2021 at 16:09 | history | asked | Manfred Weis | CC BY-SA 4.0 |