August 29, 2014
THE FIELDS INSTITUTE
FOR RESEARCH IN MATHEMATICAL SCIENCES
20th ANNIVERSARY YEAR

MATCHING, MATROIDS, AND EXTENSIONS
A Conference in Honour of Bill Cunningham's 65th Birthday

June 11,12 & 13, 2012
to be held at the


Organizing Committee:
Joseph Cheriyan (Chair), Ricardo Fukasawa,
Jim Geelen and Levent Tunçel (University of Waterloo)


The Fields Institute

University of Waterloo

Faculty of Mathematics

Department of Combinatorics & Optimization

OVERVIEW

Matroid theory and matching theory are among the oldest and most established areas in combinatorics, so progress in these areas is typically hard won; nevertheless, the recent advances have been spectacular. There is now an efficient algorithm for solving the weighted matroid matching problem for linear matroids. The 25-year old conjecture that bridgeless cubic graphs have exponentially many perfect matchings has been proved. Groundbreaking approximation algorithms for the graphical travelling salesman problem rely crucially on significant new insights on matching and T-joins. The graph minors project has been extended to binary matroids. And, a 40-year old unimodality conjecture has been proved for linear matroids.

Matroids and matching are two areas that lie close to Bill Cunningham's heart, and these advances provide the perfect backdrop to a Conference celebrating Bill's 65th birthday. As with Bill's interests, the topics covered in the Conference are not limited to matching and matroids.

SPEAKERS:

Robert Bixby (Gurobi Optimization & Rice University)

Sylvia Boyd (University of Ottawa)
Finding 2-Factors Closer to TSP in Cubic Graphs

Eddie Cheng (Oakland University)
Sufficient Conditions for Matching Preclusions and Conditional Matching Preclusions

Kevin Cheung (Carleton University)
Excursions with Matchings

Maria Chudnovsky (Columbia University)
Coloring Some Perfect Graphs

Bill Cook (Georgia Tech)
TSP Computation: Big, Small, Exact, and Approximate

Jim Geelen (U.Waterloo)
Characterizing Graphic Matroids by a System of Linear Equations

Satoru Iwata (Kyoto University)
Weighted Linear Matroid Parity

Kazuo Murota (University of Tokyo)
Discrete Legendre Duality in Matrix Pencils

Sergey Norin (McGill University)
Pairs of Disjoint Cycles

Gyula Pap (Eötvös University)
Weighted Linear Matroid Matching

Bill Pulleyblank (United States Military Academy)
Data Analytics, Sports and Optimization

Lex Schrijver (CWI)
Stable Sets and Codes

András Sebö (CNRS, G-SCOP, Grenoble)
TSP and 2ECSS with Matchings, Matroids and Extensions

Bruce Shepherd (McGill University)
From Online Colouring to Online Vector Bin Packing

Donald Wagner (Office of Naval Research)
Decomposition of 3-Connected Graphs

Francisco Zaragoza (Universidad Autónoma Metropolitana)
From Perfect Matchings to the Four Colour Theorem

SCHEDULE

All lectures are in the room DC1302 (UW, Davis Centre)
Breaks/refreshments are in DC1301 (Fishbowl, next to DC1302)
===== June 11 (Monday) =====
8:45-9:20 Registration and Coffee
9:20 Opening address
9:30-10:30 Bill Pulleyblank (United States Military Academy)
Data Analytics, Sports and Optimization
10:30-11:00 Break
11:00-12:00 Lex Schrijver (CWI)
Stable Sets and Codes
12:00-12:15 Group Photo
12:15-2:00 Lunch
2:00-3:00 Bill Cook (Georgia Tech)
TSP Computation: Big, Small, Exact, and Approximate
3:00-3:30 Bruce Shepherd (McGill University)
From Online Colouring to Online Vector Bin Packing
3:30-4:00 Break
4:00-4:30 Eddie Cheng (Oakland University)
Sufficient Conditions for Matching Preclusions and Conditional Matching Preclusions
4:30-5:30 Kazuo Murota (University of Tokyo)
Discrete Legendre Duality in Matrix Pencils
===== June 12 (Tuesday) =====
9:00-9:30 Coffee
9:30-10:30 Satoru Iwata (Kyoto University)
Weighted Linear Matroid Parity
10:30-11:00 Break
11:00-12:00 Gyula Pap (Eötvös University)
Weighted Linear Matroid Matching
12:00-2:00 Lunch
2:00-3:00 Donald Wagner (Office of Naval Research)
Decomposition of 3-Connected Graphs
3:00-3:30 Francisco Zaragoza (Universidad Autónoma Metropolitana)
From Perfect Matchings to the Four Colour Theorem
3:30-4:00 Break
4:00-4:30 Kevin Cheung (Carleton University)
Excursions with Matchings
4:30-5:30 Robert Bixby (Gurobi Optimization & Rice University)
1000X MIP Tricks
6:00 Banquet (Festival Room, South Campus Hall, UWaterloo)
===== June 13 (Wednesday) =====
9:00-9:30 Coffee
9:30-10:30

Maria Chudnovsky (Columbia University)
Coloring Some Perfect Graphs

10:30-11:00 Break
11:00-12:00 András Sebö (CNRS, G-SCOP, Grenoble)
TSP and 2ECSS with Matchings, Matroids and Extensions
12:00-2:00 Lunch
2:00-3:00 Sylvia Boyd (University of Ottawa)
Finding 2-Factors Closer to TSP in Cubic Graphs
3:00-3:30 Sergey Norin (McGill University)
Pairs of Disjoint Cycles
3:30-4:00 Break
4:00-5:00 Jim Geelen (U.Waterloo)
Characterizing Graphic Matroids by a System of Linear Equations
6:30pm Survivors Party (location: TBA)


LOCAL ARRANGEMENTS:

(a) LOCATION
All lectures will be held on the campus of the University of Waterloo. The program will begin in the morning of June 11 (Monday) and conclude in the evening of June 13 (Wednesday). There will be a banquet in the evening of June 12 (Tuesday). Further details of the program and lecture room will be provided in April.

(b) TRAVEL:
Kitchener-Waterloo is approximately 100 km from Pearson International Airport in Toronto. We recommend that you arrive in Toronto on June 10 (Sunday) and depart on June 14 (Thursday).

Ground transportation between the airport and Kitchener-Waterloo can be pre-arranged with Airways Transit by making a reservation through their web site (http://www.airwaystransit.com/). Airways Transit is a door-to-door service; they accept cash and major credit cards.

(c) ACCOMMODATIONS:
Blocks of rooms have been set aside on a first-come first-serve basis at the following hotels and university residences. When making your reservations, please quote "Bill Cunningham Conference" in order
to receive the conference rate. All rooms are air-conditioned.

COMFORT INN
Web: www.choicehotels.ca/en/comfort-hotel-cn314
Rate: $117 Cdn plus taxes/night.
Availability: Nights of June 10, 11, 12, 13.
Location: 30 minute walk to lecture room.
Cut-off-date: May 27, 2012
Name of booking: "Bill Cunningham Conference".
KING STREET RESIDENCE (Wilfrid Laurier University)
Web: http://www.laurierconferences.ca/summerAccommodations.htm
Reservation: https://accommodations.laurierconferences.ca/
Rate: $40 Cdn plus taxes/night with semi-private washroom.
$70 Cdn plus taxes/night with private washroom.
Availability: Nights of June 10, 11, 12, 13
Location: 20 minute walk to lecture room.
Cut-off-date: none.
Name of booking: "Bill Cunningham Conference".
ST. PAUL'S RESIDENCE (University of Waterloo)
Web: http://www.stpauls.uwaterloo.ca/hotel/guest_rooms.html
Rate: $45 Cdn plus taxes/night for single room with shared washrooms.
Availability: Nights of June 10, 11, 12, 13
Location: 10 minute walk to the lecture room.
Cut-off-date: none.
Name of booking: "Bill Cunningham Conference".
WATERLOO INN CONFERENCE HOTEL
Web: www.waterlooinn.com
Rate: $145 Cdn plus taxes/night.
Availability: Nights of June 10, 11, 12 [June 13 is sold out].
Location: 30-35 minute walk from the lecture room.
Cut-off-date: May 4, 2012.
Name of booking: "Bill Cunningham Conference".

(d) For further information, please send email to bc65<at>uwaterloo.ca


Confirmed Participants as of June 10, 2012

Full Name University/Affiliation
Abdallah, Mohamad Oakland University
Abdi, Ahmad University of Waterloo
Ahmadian, Sara University of Waterloo
Allaire, Francis Lakehead University
Au, Gary University of Waterloo
Barrera-Cruz, Fidel University of Waterloo
Basu, Deepan Indian Statistical Institute
Bixby, Robert. E. Rice University
Boyd, Sylvia University of Ottawa
Cameron, Kathleen Wilfrid Laurier University
Cheng, Eddie Oakland University
Cheriyan, Joseph University of Waterloo
Cheung, Kevin Carleton University
Chudnovsky, Maria Columbia University
Connolly, Robert Oakland University
Cook, Bill Georgia Institute of Technology
Cunningham, Bill University of Waterloo
Davis, James Cornell University
Faenza, Yuri UniversitÓ di Padova
Fan, Xiaoxia University of Waterloo
Farzad, Babak Brock University
Friggstad, Zachary University of Waterloo
Fukasawa, Ricardo University of Waterloo
Fung, Issac University of Waterloo
Gao, Zhihan University of Waterloo
Geelen, Jim University of Waterloo
Georgiou, Konstantinos University of Waterloo
Godsil, Chris University of Waterloo
Goulden, Ian University of Waterloo
Guenin, Bertrand University of Waterloo
Guo, Krystal Simon Fraser University
Guruganesh, Guru University of Waterloo
Hartnell, Bert Saint Mary's University
Hartvigsen, David University of Notre Dame
Haxell, Penny University of Waterloo
Hongo, PatrÝcia University of Campinas
Huynh, Tony KAIST
Isbrandt, Stan  
Iwata, Satoru Kyoto University
Jenkyns, Tom Brock University
Jeong, Jisu KAIST
Kapadia, Rohan University of Waterloo
Karimi, Mehdi University of Waterloo
Kiraly, Zoltan Eotvos University
Konemann, Jochen University of Waterloo
Kothari, Nishad University of Waterloo
Kwon, O-joung Korea Advanced Institute of Science and Technology
Laekhanukit, Bundit McGill University
Li, Zhentao ENS Lyon
Liptak, Laszlo Oakland University
Lo, Venus University of Waterloo
Martin, William Worcester Polytechnic Institute
McGuinness, Sean Thompson Rivers University
Menezes, Alfred University of Waterloo
Minooei, Hadi University of Waterloo
Mosca, Michele University of Waterloo
Mullin, Ronald University of Waterloo
Murota, Kazuo University of Tokyo
Murty, Uppaluri University of Waterloo
Myklebust, Tor University of Waterloo
Nayak, Ashwin University of Waterloo
Newman, Mike University of Ottawa
Norin, Sergey McGill University
Pandey, Devanshu University of Waterloo
Pap, Gyula Eotvos University
Park, Jeongmi Pusan National University
Pritchard, David University of Waterloo
Pulleyblank, Bill United States Military Academy, West Point
Qian, David University of Waterloo
Rardin, Ronald University of Arkansas
Richmond, Bruce University of Waterloo
Sadeghian, Sina University of Waterloo
Sanita, Laura University of Waterloo
Sano, Yoshio National Institute of Informatics
Sato, Cristiane University of Waterloo
Schellenberg, Paul University of Waterloo
Schrijver, Lex Centrum voor Wiskunde en Informatica
Seb÷, Andrßs CNRS G-SCOP
Sharpe, Malcolm University of Waterloo
Shepherd, Bruce McGill University
Silva, Marcel University of Waterloo
Silva, Ruan University of Campinas
Sivaraman, Vaidyanathan The Ohio State University
Steffy, Daniel Oakland University
Stuive, Leanne University of Waterloo
Swamy, Chaitanya University of Waterloo
Szestopalow, Michael University of Waterloo
Teske-Wilson, Edlyn University of Waterloo
Tunšel, Levent University of Waterloo
van Beek, Peter University of Waterloo
van Zwam, Stefan Princeton University
Vanstone, Scott University of Waterloo
Vegh, Laszlo Georgia Institute of Technology
Wagner, Donald Office of Naval Research
Wang, Hanson University of Waterloo
Weir, Brandon University of Waterloo
Wormald, Nicholas University of Waterloo
Younger, Dan University of Waterloo
Zaragoza, Francisco UAM Azcapotzalco

 

Top