Sufficiency of the NR-facet condition for parsimonious relaxations
Sufficiency of the NR-facet condition for parsimonious relaxations
Let be the Graphical Traveling Salesman Polyhedron, let be the graph associated with a relaxation , and call a facet of an NR-facet when it has the stated non-rank property. Parsimonious-relaxation conjecture. If every connected component of contains a vertex corresponding to an NR-facet of , then the relaxation has the parsimonious property. This conjectures that the necessary condition established in the cited theorem is also sufficient; the supplied text gives no resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Dirk Oliver Theis, “On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra”, arXiv:0712.1269 (2009).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.