Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem

100%

Sierksma G.

Applicationes Mathematicae

1993-1995

tom 22

nr 3

351-358

The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived for the diameters of the 3-Interchange Graph and the union of the 2- and the 3-Interchange Graphs. Finally, some new adjacency properties for the Asymmetric Traveling Salesman Polytope and the Assignment Polytope are given.

On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems

63%

Ghosh D., Sierksma G.

Applicationes Mathematicae

2003

tom 30

nr 3

305-313

This paper studies the complexity of sensitivity analysis for optimal and ε-optimal solutions to general 0-1 combinatorial optimization problems with min-max objectives. Van Hoesel and Wagelmans [9] have studied the complexity of sensitivity analysis of optimal and ε-optimal solutions to min-sum problems, and Ramaswamy et al. [17] the complexity of sensitivity analysis of optimal solutions to min-max problems. We show that under some mild assumptions the sensitivity analysis of ε-optimal solutions to min-max problems is easy if and only if the original problem is easy. This result is interesting since it immediately applies to a large number of problems, and also because the technique used to prove it is different from the ones used in the related papers (for example, in [17] and [9]).

Ograniczanie wyników

2 Applicationes Mathematicae

2 Sierksma G.

1 Ghosh D.

1 2003

1 1994

Wyniki wyszukiwania

Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem

On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems