Conference on Integer Programming and Combinatorial Optimization IPCO XV

June 15 - 17, 2011
IBM T.J. Watson Research Center in Yorktown Heights, New York

Organizers:

Sanjeeb Dash, IBM, ipco2011help@gmail.com

Oktay Günlük, IBM, ipco2011help@gmail.com

Jon Lee, IBM, ipco2011help@gmail.com

Maxim Sviridenko, IBM, ipco2011help@gmail.com

Workshop Program:

Wednesday, June 15, 2011

 9:30 - 10:00  Constructing Extended Formulations from Reflection Relations
               Volker Kaibel and Kanstantsin Pashkovich

10:00 - 10:30  A Subexponential Lower Bound for Zadeh'S Pivoting Rule for Solving Linear Programs and Games
               Oliver Friedmann

10:30 - 11:00  A Probabilistic Analysis of the Strength of the Split and Triangle Closures
               Amitabh Basu, Gerard Cornuejols and Marco Molinaro

11:00 - 11:30  Coffee break

11:30 - 12:00  Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
               Fabrizio Grandoni and Thomas Rothvoss

12:00 - 12:30  Facility Location with Client Latencies: Linear-Programming Based Techniques for Minimum-Latency Problems
               Deeparnab Chakrabarty and Chaitanya Swamy

12:30 -  1:00  Approximability of Capacitated Network Design
               Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna and Nitish Korula

 1:00 -  2:30  Lunch

 2:30 -  3:00  Valid Inequalities for the Pooling Problem with Binary Variables
               Claudia D'Ambrosio, Jeff Linderoth and James Luedtke

 3:00 -  3:30  Discrete Convexity and Faster Algorithms for Weighted Matching Forests
               Kenjiro Takazawa

 3:30 -  4:00  Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
               Anna Karlin, Claire Mathieu and Thach Nguyen

 4:00 -  4:30  Coffee break

 4:30 -  5:00  An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming
               Bissan Ghaddar, Juan Vera and Miguel Anjos

 5:00 -  5:30  Lift-and-Project Cuts for Mixed Integer Convex Programs
               Pierre Bonami

 5:30 -  6:00  Convexification Techniques for Linear Complementarity Constraints
               Trang Nguyen, Mohit Tawarmalani and Jean-Philippe Richard

Thursday, June 16, 2011

 9:30 - 10:00  Fixed-Charge Transportation On a Path: Linear Programming Formulations
               Mathieu Van Vyve

10:00 - 10:30  An Excluded Minor Characterization of Seymour Graphs 
               Alexander Ageev, Yohann Benchetrit, Andras Sebo and Zoltan Szigeti

10:30 - 11:00  Contact Center Scheduling with Strict Resource Requirements
               Aman Dhesi, Pranav Gupta, Amit Kumar, Gyana Parija and Sambuddha Roy

11:00 - 11:30  Coffee break

11:30 - 12:00  Degree Bounded Forest Covering
               Tamas Kiraly and Lap Chi Lau

12:00 - 12:30  A Primal-Dual Algorithm for Weighted Abstract Cut Packing
               S. Thomas Mccormick and Britta Peis

12:30 -  1:00  Iterative Packing for Demand Matching and Sparse Packing
               Ojas Parekh

 1:00 -  2:30  Lunch

 2:30 -  3:00  A Layered Graph Model and an Adaptive Layers Framework To Solve Delay-Constrained Minimum Tree
               Mario Ruthmair and Günther Raidl

 3:00 -  3:30  Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
               Satoru Iwata and Mizuyo Takamatsu

 3:30 -  4:00  Capacitated Vehicle Routing with Non-Uniform Speeds
               Inge Gortz, Marco Molinaro, Viswanath Nagarajan and R Ravi

 4:00 -  4:30  Coffee break

 4:30 -  5:00  Design and Verify: A New Scheme for Generating Cutting-Planes
               Santanu S. Dey and Sebastian Pokutta

 5:00 -  5:30  Complexity Analyses of Bienstock-Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
               Yu Hin Au and Levent Tuncel
 5:30 -  6:00  On the Chvatal-Gomory Closure of a Compact Convex Set
               Daniel Dadush, Santanu S. Dey and Juan Pablo Vielma

Friday, June 17, 2011

 9:30 - 10:00  A New Approach to the Stable Set Problem Based on Ellipsoids
               Monia Giandomenico, Adam Letchford, Fabrizio Rossi and Stefano Smriglio
 
10:00 - 10:30  Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation
               Martin Bergner, Alberto Caprara, Fabio Furini, Marco Lübbecke, Enrico Malaguti and Emiliano Traversi

10:30 - 11:00  Jump Number of Two-Directional Orthogonal Ray Graphs
               Jose A. Soto and Claudio Telha

11:00 - 11:30  Coffee break

11:30 - 12:00  An Exact Rational Mixed-Integer Programming Solver
               William Cook, Thorsten Koch, Daniel Steffy and Kati Wolter

12:00 - 12:30  Backdoor Branching
               Matteo Fischetti and Michele Monaci

12:30 -  1:00  Safe Lower Bounds for Graph Coloring
               Stephan Held, Edward C. Sewell and William Cook

 1:00 -  2:30  Lunch

 2:30 -  3:00  TSP on Cubic and Subcubic Graphs
               Sylvia Boyd, Rene Sitters, Suzanne Van Der Ster and Leen Stougie

 3:00 -  3:30  Universal Packet Routing with Arbitrary Bandwidths and Transit Times
               Britta Peis and Andreas Wiese

 3:30 -  4:00  Set Covering with Ordered Replacement - Additive and Multiplicative Gaps
               Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoss and Laura Sanità

 4:00 -  4:30  Coffee break

Previous: Participation

Workshop Index

DIMACS Homepage