Combinatorial Optimization Day

McMaster University Advanced Optimization Laboratory

August 22, 2008

ITB 201

Time	Talk
14:00 - 14:45	On semidefinite programming relaxations of the traveling salesman problem Etienne de Klerk (Universiteit van Tilburg) We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: D. Cvetković, M. Cangalović and V. Kovačević-Vujčić. Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem. In Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, 1999, 126-136, Springer-Verlag, London, UK. Unlike the bound of Cvetković et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
14:45 - 15:30	On Subtour Patching for the Traveling Salesman Problem George Steiner (McMaster University - DeGroote School of Business) A large variety of scheduling problems has recently been shown to be solvable by applying subtour patching to the Traveling Salesman Problem (TSP) on permuted Monge matrices. Although the TSP on permuted Monge matrices is known to be strongly NP-hard, we present polynomial-time solutions for many of the special cases generated by the scheduling problems. We also show that a simple subtour-patching heuristic is asymptotically optimal for the TSP on permuted Monge matrices under some mild technical conditions.
15:30 - 15:45	Break
15:45 - 16:15	Parallelization of Constraint-based Scheduling on Blue Gene Feng Xie (McMaster University, IBM Research - Yorktown Heights) Scheduling is the problem of allocating scarce resources to activities over time, which can be modeled as a Constraint Satisfaction Problem with temporal and resource constraints. The solver, basically a backtracker equipped with various heuristics for constraint propagation, is suitable for parallelization. I will demonstrate the challenges we faced in the effort to parallelize the solver using MPI on Blue Gene, as well as the approaches we take to create a scalable parallelized scheduling solver.
16:15 - 16:45	Intersecting Families of Permutations Haran Pilpel (Hebrew University of Jerusalem) Two permutations in Sn are 1-intersecting if they agree on some point. A subset A of Sn is 1-intersecting if every two elements are 1-intersecting. The maximal measure of a 1-intersecting family is 1/n (Deza-Frankl) and all such families are known (Cameron-Ku, Larose-Malvenuto.) We study families which are almost maximal, i.e. have measure almost 1/n. To get stability results, the natural instrument is Fourier analysis. Since Sn is nonabelian, we need to understand its irreducible representations. We characterize all 1-intersecting families of measure > 1/n - c/n6. Joint work with Ehud Friedgut.
16:45 - 17:15	Extended results on the Oberwolfach problem William Hua (McMaster University) The Oberwolfach problem asks if it is possible to decompose the complete graph K2k+1 into k 2-regular spanning subgraphs (2-factors) such that all 2-factors are isomorphic to a given 2-regular graph. An extension of the problem to even orders asks if this is possible for K2k+2 \ I, where I is a 1-regular spanning subgraph. We demonstrate that for orders between 18 and 40, the Oberwolfach problem can be answered in the affirmative.