=====================================================================
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))
=====================================================================