Title: Rare Events in Combinatorial Optimization: The Metric TSP Case and
Bin-packing


Moshe Dror
MIS Department, Eller School of Management, University of
Arizona, Tucson, Arizona.


(In collaboration with Yusin Lee, James B. Orlin, and Michael Zhu)


Abstract:

In the first part of this talk we will examine the relation between the length
of an optimal traveling salesman tour and the sum of its nodes' marginal values
(a node's marginal value is the difference between the length of an optimal TSP
tour over a given node set and the length of an optimal TSP tour over the node
set minus the node). To our knowledge, this problem has not been studied
previously. We restrict our analysis to the metric space l_p2 and consider
norms $L_1 (L_{\infty}),L_{4/3},L_2,L_4. The event in which the sum of TSP
marginal values is greater than the length of the optimal tour is rare. We
present a number of cases for which the sum of marginal values is never greater
than that for the optimal tour. We establish a worst case ratio of 2 for any
metric TSP. In addition, for 6 node TSPs we determine the worst ratio for the
L_1 (L_{\infty}) norm, triangle inequality, and symmetric distance, of 10/9,
1.2, and 1.5 respectively, by solving the appropriate mixed integer programming
problems. In the second part of this talk we examine the likelihood that two
shelves of integer length L can be packed with items whose individual lengths
are divisors of L, given that the individual items sum-up to 2L. The main
thrust of this study is computational. That is, we explicitly compute the
answer for this question for all integers L, 1\leq L\leq 1000. We conclude that
an instance of this packing problem in which we cannot pack the two shelves is
very rare. Existence of packing failures is tied to the number of divisors of
L. That is, we prove that the number of divisors has to be at least 8 for a
packing failure to exist.