Skip to main content
MathOverflow

Return to Question

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

It is well known, that the optimal tours are invariant under the addition of vertex weights; it is also known, that minimum spanning trees provide an upper bound on the length of the shortest Hamilton cycle in a graph and, that the MST is sensitive to the addition/subtraction of vertex weights, which makes it possible to penalize vertices with high degree in the MST and thus improve the upper bound in some cases.

Questions:

 

are TSP algorithms, that are based on polyhedral methods, such as e.g. Cut&Branch, sensitive to the addition/subtraction of vertex weights in the sense, that the execution path from the input of a TSP instance to reporting the optimal solutions can vary, if vertex weights are added/subtracted?

 

In case of an affirmative answer: what would be good criteria for the vertex weights to be added/subtracted (e.g. maximize sum of subtracted weights, that leave all edge weights non-negative; add large weights; add random weights)?

It is well known, that the optimal tours are invariant under the addition of vertex weights; it is also known, that minimum spanning trees provide an upper bound on the length of the shortest Hamilton cycle in a graph and, that the MST is sensitive to the addition/subtraction of vertex weights, which makes it possible to penalize vertices with high degree in the MST and thus improve the upper bound in some cases.

Questions:

 

are TSP algorithms, that are based on polyhedral methods, such as e.g. Cut&Branch, sensitive to the addition/subtraction of vertex weights in the sense, that the execution path from the input of a TSP instance to reporting the optimal solutions can vary, if vertex weights are added/subtracted?

 

In case of an affirmative answer: what would be good criteria for the vertex weights to be added/subtracted (e.g. maximize sum of subtracted weights, that leave all edge weights non-negative; add large weights; add random weights)?

It is well known, that the optimal tours are invariant under the addition of vertex weights; it is also known, that minimum spanning trees provide an upper bound on the length of the shortest Hamilton cycle in a graph and, that the MST is sensitive to the addition/subtraction of vertex weights, which makes it possible to penalize vertices with high degree in the MST and thus improve the upper bound in some cases.

Questions:

are TSP algorithms, that are based on polyhedral methods, such as e.g. Cut&Branch, sensitive to the addition/subtraction of vertex weights in the sense, that the execution path from the input of a TSP instance to reporting the optimal solutions can vary, if vertex weights are added/subtracted?

In case of an affirmative answer: what would be good criteria for the vertex weights to be added/subtracted (e.g. maximize sum of subtracted weights, that leave all edge weights non-negative; add large weights; add random weights)?

Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Influence of Vertex Weights on Performance of Polyhedral TSP Algorithms

It is well known, that the optimal tours are invariant under the addition of vertex weights; it is also known, that minimum spanning trees provide an upper bound on the length of the shortest Hamilton cycle in a graph and, that the MST is sensitive to the addition/subtraction of vertex weights, which makes it possible to penalize vertices with high degree in the MST and thus improve the upper bound in some cases.

Questions:

are TSP algorithms, that are based on polyhedral methods, such as e.g. Cut&Branch, sensitive to the addition/subtraction of vertex weights in the sense, that the execution path from the input of a TSP instance to reporting the optimal solutions can vary, if vertex weights are added/subtracted?

In case of an affirmative answer: what would be good criteria for the vertex weights to be added/subtracted (e.g. maximize sum of subtracted weights, that leave all edge weights non-negative; add large weights; add random weights)?