===================================================================== Titles and Abstracts Bixby, Boyd, Cheng, Cheung, Chudnovsky, Cook, Geelen, Iwata, Norin, Pap, Pulleyblank, Schrijver, Sebo, Wagner, Zaragoza ===================================================================== Bob Bixby Reminiscences on Matroids, and 1000x Tricks for Mixed Integer Programming Abstract: Part 1 -- I will take a look back at what is now really a footnote given the remarkable recent developments in matroid theory, the characterization of matroids representable over GF(3). Part 2 -- A modern MIP solver is built on several pillars. In addition to a rich theoretical base, a MIP solver also builds on simple observations about problem structure found in practical models. This talk will discuss several 'tricks' for exploiting such structure. The unifying theme: each of these tricks allows us to solve some real models at least 1000X faster than without them. (Joint work with Ed Rothberg and Zonghao Gu) ===================================================================== Sylvia Boyd Finding 2-Factors Closer to TSP in Cubic Graphs Abstract: The lower bound for the TSP provided by the 2-factor problem can be improved by finding a 2-factor that covers certain prescribed edge-cuts in the graph. This is closely related to the problem of finding 2-factors which do not contain any cycles of prescribed lengths, a problem studied by Cunningham and Wang. We present an algorithm and polyhedral results for the problem of finding a minimum-weight 2-factor covering all the 3-edge cuts in weighted bridgeless cubic graphs. We further give an algorithm for finding a 2-factor covering all the 3- and 4-edge cuts in bridgeless cubic graphs, and show such a 2-factor can be used to obtain a 6/5-approximation algorithm for finding a minimum size 2-edge connected subgraph in 3-edge connected cubic graphs. We also discuss recent results on the related problem of finding 2-factors which do not contain any 3 or 4 cycles. (Joint work with Satoru Iwata and Kenjiro Takazawa) ============================================================== Eddie Cheng Sufficient Conditions for Matching Preclusions and Conditional Matching Preclusions Abstract: Let $G$ be an $r$-regular graph with an even number of vertices. We define a \emph{matching preclusion set} to be a set of edges whose deletion results in a graph with no perfect matchings, and we define the cardinality of such an optimal set to be the \emph{matching preclusion number}, denoted by $\mbox{mp}(G)$. If $G$ is bipartite, then Hall's Theorem implies that $\mbox{mp}(G)=r$. Plesn\'ik proved that this is true in general if $G$ is $(r-1)$-edge-connected. A trivial matching preclusion set is a set of edges incident to a single vertex $v$, that is $\delta(v)$. $G$ is \emph{super matched} if every optimal matching preclusion set is trivial, that is, the only optimal obstruction sets are of the form $\delta(v)$, whose deletion creates an isolated vertex. We define a \emph{conditional matching preclusion set} to be a set of edges whose deletion results in a graph with no isolated vertices and no perfect matchings, and we define the cardinality of such an optimal set to be the \emph{conditional matching preclusion number}, denoted by $\mbox{mp}_1(G)$. A trivial conditional matching preclusion set can be constructed as follows: Take any 2-path $u-v-w$ and consider $\delta(u)\cup\delta(w)\setminus\{(u,v),(v,w)\}$. So an upper bound for $\mbox{mp}_1(G)$ is $2r-2$ or $2r-3$ depending on whether $G$ is triangle-free. $G$ is \emph{conditionally super matched} if every optimal matching preclusion set is trivial. In this talk, we consider sufficient conditions that are in the same spirit of Plesn\'ik's Theorem for $G$ to be super matched, for $\mbox{mp}_1(G)$ to attain the trivial upper bound, and for $G$ to be conditionally super matched. (Joint work with Philip Hu, Roger Jia, Marc Lipman and L\'aszl'o Lipt\'ak) ===================================================================== Kevin Cheung Excursions with Matchings Abstract: A few years ago, I was asked to take over the task of assigning teaching assistants to courses offered by the School of Mathematics and Statistics, Carleton University. A simplified version of the problem could be modeled as a maximum-weight matching problem with side constraints. It turned out that the problem instances were usually not computationally challenging. However, having been at the job for over three years, I learned that matching teaching assistants to courses is still as much an art as a science. In this talk, I will discuss some of the surprises that I encountered and how I eventually dealt with some of them with varied success. ============================================================== Maria Chudnovsky Coloring Some Perfect Graphs Abstract: A graph G is called perfect if for every induced subgraph H of G, the chromatic number and the clique number of H are equal. After the recent proof of the Strong Perfect Graph Theorem, and the discovery of a polynomial-time recognition algorithm, the central remaining open question about perfect graphs is finding a combinatorial polynomial-time coloring algorithm. (There is a polynomial-time algorithm known, using the ellipsoid method). Recently, we were able to find such an algorithm for a certain class of perfect graphs, that includes all perfect graphs admitting no balanced skew-partition. The algorithm is based on finding special "extremal" decompositions in such graphs; we also use the idea of "trigraphs". (Joint work with Nicolas Trotignon, Theophile Trunck and Kristina Vuskovic) ============================================================== Bill Cook TSP Computation: Big, Small, Exact, and Approximate Abstract: We discuss dynamic programming, Held-Karp 1-trees, 2-factors, and LP methods for obtaining lower bounds for the traveling salesman problem. Combining decomposition techniques for building cutting planes and a parallel barrier LP solver, we compute in under 3 minutes of wall-clock time a lower bound that is within 0.01% of the best known tour for a 100,000-city test instance. (Joint work with David Applegate) ============================================================== Jim Geelen Characterizing Graphic Matroids by a System of Linear Equations Abstract: Given a rank-r binary matroid we construct a system of O(r^3) linear equations in O(r^2) variables that has a solution over GF(2) if and only if the matroid is graphic. (Joint work with Bert Gerards) ===================================================================== Satoru Iwata Weighted Linear Matroid Parity Abstract: The matroid parity problem was introduced as a common generalization of matching and matroid intersection problems. In the worst case, it requires an exponential number of independence oracle calls. Nevertheless, Lovasz (1980) showed that the problem is solvable in polynomial time if the matroid in question is represented by a matrix. Subsequently, efficient algorithms have been developed for this linear matroid parity problem. This talk presents a combinatorial, deterministic, strongly polynomial algorithm for its weighted version. The algorithm builds on a polynomial matrix formulation of the problem using Pfaffian and an augmenting path algorithm for the unweighted version by Gabow and Stallmann (1986). Independently of this work, Gyula Pap has obtained the same result based on a different approach. ===================================================================== Kazuo Murota Discrete Legendre Duality in Matrix Pencils Abstract: Matchings and matroids are useful tools in combinatorial study of matrices. For the Kronecker form of matrix pencils, two linear-algebraic characteristics have been featured: degrees of subdeterminants and ranks of expanded matrices, both enjoying discrete convexity. We show the discrete Legendre dualities between the two characteristics and also between their combinatorial bounds in terms of matchings. This reveals that the tightness of one of the combinatorial bounds is equivalent to that of the other. A sufficient condition for the tightness is given, and its application to electric networks is indicated. Furthermore, this result is extended to the matroid-theoretic analysis of mixed matrix pencils. ===================================================================== Sergey Norin Pairs of Disjoint Cycles Abstract: We will describe a polynomial-time algorithm which determines whether an input graph contains a pair of disjoint cycles with the given property. In particular, it allows one to test whether a graph has two disjoint odd cycles, whether it has two disjoint cycles, one non-zero modulo 3 and the other non-zero modulo 5, whether a graph embedded in a surface has two disjoint homologically non-trivial cycles, and whether a given embedding of a graph in 3-space is linkless. The algorithm is based on an efficient characterization of the span of a certain collection of matrices indexed by pairs of disjoint cycles, extending a theorem of van der Holst and a characterization of linklessly embeddable graphs due to Robertson, Seymour and Thomas. (Joint work with Hein van der Holst and Robin Thomas) ===================================================================== Gyula Pap Weighted Linear Matroid Matching Abstract: Matroid matching is a fundamental model introduced by Lawler that generalizes graph matching and matroid intersection. Although the problem turned out to be NP-hard for general matroids, Lov\'asz proved that it can be solved in polynomial time for linear matroids. As with many combinatorial optimization problems, we can investigate the weighted version of linear matroid matching, and until recently, this problem was unsolved. 2011 results by Ho Yee Cheung show that weighted linear matroid matching can be solved with a randomized algebraic algorithm in polynomial time. To design a deterministic algorithm, two independent, fundamentally different approaches have emerged in the last couple of months - one by Satoru Iwata, and another one that is the main topic of this talk. This approach is based on the combination of concepts from our 2008 paper with Dion Gijswijt on matroid fractional matching, and structural properties similar to those in Vande Vate and Orlin's (unweighted) linear matroid matching algorithm. Thus we obtain a strongly polynomial primal-dual algorithm, in which duality is stated with an extended LP formulation. In a nutshell, the algorithm runs quite similar to Edmonds' matching algorithm in that it contracts blossoms and changes dual values, until optimality is achieved. However, it also differs from Edmonds' algorithm in that it does not maintain an alternating forest - instead it only applies a black-box for the unweighted problem to an auxiliary instance. ===================================================================== William Pulleyblank Data Analytics, Sports and Optimization Abstract: Recently, optimization and data analysis problems involving sports have received considerable attention. In part this is because of the availability of data and in part is because these problems provide interesting non-classified examples of force-on-force operations. I will discuss three such problems: helping Army beat Navy at football, which has not happened for nine years, helping the New York Yankees to a more effective job of scheduling their scouting operations and optimizing a problem related to the announced, but unexecuted reorganization of the National Hockey League. ===================================================================== Alexander Schrijver Stable Sets and Codes Abstract: Finding a maximum-size stable set in a graph is a hard problem. A special case is finding maximum-size error-correcting codes, where the graphs have even exponential size. Delsarte and Lovasz gave good upper bounds, using linear and semidefinite programming. We extend these methods with tools from representation theory and C*-algebra, yielding sharper code bounds. For instance, it gives A(20,8)=256, that is, the maximum number of 0,1 words of length 20 any two of which have Hamming distance at least 8, is equal to 256. In other words, the quadruply shortened Golay code is optimum. In the talk we give an introduction to the methods and results. (Joint work with Dion Gijswijt and Hans Mittelmann) ===================================================================== Andras Sebo TSP an 2ECSS with Matchings, Matroids and Extensions Abstract: We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graphic TSP itself, we improve the approximation ratio to $7/5$. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio $3/2$. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest $2$-edge-connected spanning subgraph is $4/3$. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs, a particular matroid intersection problem. Matchings, Joins, Matroids are the key-words of this approach, and I learnt a lot about all of these from Bill. We obtain the same new bounds on the integrality gaps of the corresponding polyhedra, some of which are tight. (Joint work with Jens Vygen) ===================================================================== Bruce Shepherd From Online Colouring to Online Vector Bin Packing Abstract: We discuss an older lower bound on the performance ratio for online colouring. We then show how it yields a lower bound for online vector bin packing for bins with capacity B. The bounds are tight for B=1, but suggest several interesting upper bound questions (for colouring and bin packing) for larger B. (Joint work with Y.Azar, S.Kamara) ===================================================================== Donald Wagner Decomposition of 3-Connected Graphs Abstract: This talk presents two results on the decomposition of 3-connected graphs. The first result is that every 3-connected graph has a unique decomposition, each member of which is either cyclically 4-connected or highly decomposable. The second result is concerned with 3-connected graphs that do not contain K_{3,3} minor through a fixed edge. Every graph in this class is shown to have a unique decomposition, each member of which is planar or nearly planar. ===================================================================== Francisco Zaragoza From Perfect Matchings to the Four Colour Theorem Abstract: A unimodular triangle has integer vertices and area one half. Consider a partition into unimodular triangles (a unimodular triangulation) of a rectangle with integer vertices and sides parallel to the axis of the plane. A well-known and nice results says that the dual of this triangulation, seen as a graph, has a perfect matching. We are interested on studying some properties of the graphs that can be obtained as unimodular triangulations of general polygons with integer vertices. We showed first that maximal outerplanar graphs can be obtained in this way. We recently showed that all planar graphs can be obtained as subgraphs of unimodular triangulations of polygons with integer vertices. This result turns out to be equivalent to the Four Colour Theorem. (Joint work with Gloria Aguilar (Cinvestav), David Flores (UNAM), Sergio Prez (UAM), Francisco Santos (U Cantabria)) =====================================================================