Talk:Held–Karp algorithm

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

This page was originally written by the user LIU CS MUN. I just added it here. I suggest posting suggestions for changes that should be made here, in the page's talk section, so we can collaboratively work on it. I'd definitely use this page on Wikipedia, since I'm studying algorithms. Boris Jakovljević (talk) 08:47, 13 January 2015 (UTC)Reply

The endash breaks link parsing algorithms in many websites(including Facebook). This is not that major of a change, but feedback is appreciated. Going to change the title for now. — Preceding unsigned comment added by Xrisk (talk • contribs) 04:51, 18 December 2015 (UTC)Reply

No, don't. They mean different things and a hyphen would be incorrect., Hyphens are for one person with a double-barreled name, like Lotho Sackville-Baggins. En-dashes are for two different people. That way you can tell e.g. from the name of the Birch–Swinnnerton-Dyer conjecture that it is named after two people (Birch and Swinnnerton-Dyer), not three. You're free to link to the name with the incorrect hyphen elsewhere — Held-Karp algorithm should be a redirect pointing to the same article — but you shouldn't actually change the title here. It would be a violation of our Manual of Style, MOS:DASH: "When naming an article, do not use a hyphen (-) as a substitute for an en dash that properly belongs in the title".

There is, however, a different problem with the title: there's an unrelated TSP heuristic also called the Held–Karp algorithm (or Held–Karp heuristic), which we should have an article on, and this one should also have Bellman's name attached to it. —David Eppstein (talk) 06:01, 18 December 2015 (UTC)Reply

Thanks for letting me know that. It's difficult for occasional editors to know the entirety of Wikipedia protocol. I have a question though, why doesn't Wikipedia change the endash to it's appropriate escape code (%E2%80%93) in the URL? Xrisk 13:58, 18 December 2015 (UTC)

When I copy and paste the Wikipedia url from my browser to another app I get it encoded in exactly that way. —David Eppstein (talk) 17:09, 18 December 2015 (UTC)Reply

"sTSP can be considered, in many cases, as a subproblem of the aTSP." Perhaps I'm missing something, but I cannot find a single case in which it is not. I would suggest removing "in many cases" since it gives the impression that it does not in fact hold in all cases. Correct me if I'm wrong.

Stirling's approximation of the complexity of exhaustive enumeration ‒ I don't see why this is here. Aren't we all sufficiently familiar with the factorial function? Again, I suggest removing.

I would rather see the definitions of sTSP, aTSP and mTSP in the TSP article; especially since mTSP is not even referred to in this article after the definition, and the only statement pertaining to it is "The mTSP is generally treated as a relaxed vehicle routing problem.", which, again, does not belong to this article. 147.229.208.56 (talk) 03:05, 12 February 2020 (UTC)Reply

"TSP is an extension of the Hamiltonian circuit problem." I think this can be misleading: in the Hamiltonian circuit problem the problem comes from the fact that there is a fixed graph in input; there is no such thing in the TSP problem as any point can be linked with any point. — Preceding unsigned comment added by Baba Arouj (talk • contribs) 13:27, 28 May 2021 (UTC)Reply

There is no important difference, for exact rather than approximate solutions, between having an unweighted graph as input, or having as input a system of distances with two distinct values (the smaller of which corresponds to the graph edges). —David Eppstein (talk) 18:39, 28 May 2021 (UTC)Reply

The algorithm example is not in line with the provided pseudocode, neither in naming nor in behaviour (apparently).