## Scientific Program Cluster Details

Please login, if you want to personalize your selection of clusters.

### Cluster: Combinatorial optimization

#### Monday

**10:30 - 12:00, room: H 3004**

**Chair: Stephan Held**

Combinatorial optimization in chip design I

Markov | A primal-dual Lagrange optimization for VLSI global placement [...] |

Struzyna | Quadratic and constrained placement in chip design: Global flows and local realizations [...] |

Brenner | Fractional versus integral flows: A new approach to VLSI legalization [...] |

**10:30 - 12:00, room: H 3005**

**Chair: Lionel Pournin**

Triangulations

Pournin | The flip-graph of the 4-dimensional cube is connected [...] |

Schmiedl | Gromov-Hausdorff distance of finite metric spaces [...] |

**10:30 - 12:00, room: H 3008**

**Chair: Vijay V. Vazirani**

Rational convex programs and combinatorial algorithms for solving them

Vazirani | Rational convex programs [...] |

Jain | Eisenberg-Gale markets: Algorithms and game theoretic properties [...] |

Goel | A perfect price discrimination market model, and a rational convex program for it [...] |

**10:30 - 12:00, room: H 3012**

**Chair: Sigrid Knust**

Matching

Knust | Scheduling sports tournaments on a single court based on special 2-factorizations [...] |

Takamatsu | Matching problems with delta-matroid constraints [...] |

Kapralov | On the communication and streaming complexity of maximum bipartite matching [...] |

**10:30 - 12:00, room: H 3013**

**Chair: Ralf Borndörfer**

Combinatorial optimization in railways I

Imaizumi | A column generation approach for crew rostering problem in a freight railway company in Japan [...] |

Schlechte | Recent developments in railway track allocation [...] |

Weider | A rapid branching method for the vehicle rotation planning problem [...] |

**10:30 - 12:00, room: H 3021**

**Chair: Nikhil Bansal**

Scheduling algorithms I

Pruhs | Online primal-dual for non-linear optimization with applications to speed scaling [...] |

Svensson | On the hardness of scheduling with precedence constraints to minimize makespan [...] |

Stein | How to schedule when you have to buy your energy [...] |

**13:15 - 14:45, room: H 3004**

**Chair: Ulrich Brenner**

Combinatorial optimization in chip design II

Suhl | Lagrangian relaxation and quadratic minimum cost flows for gate sizing [...] |

Bartoschek | Fast buffering of repeater trees [...] |

Held | Delay bounded Steiner trees and time-cost tradeoffs for faster chips [...] |

**13:15 - 14:45, room: H 3005**

**Chair: Paul Wollan**

Structural graph theory and methods

Oum | Vertex-minors and pivot-minors of graphs [...] |

Joret | Excluded forest minors and the Erdös-Pósa Property [...] |

Norine | Pairs of disjoint cycles [...] |

**13:15 - 14:45, room: H 3008**

**Chair: Satoru Fujishige**

Discrete structures and algorithms I

Kijima | Efficient randomized rounding in permutahedron [...] |

Pap | Characterizing and recognizing generalized polymatroids [...] |

Massberg | Dual consistency and cardinality constrained polytopes [...] |

**13:15 - 14:45, room: H 3012**

**Chair: George Steiner**

Scheduling I

Rieger | Two variants of flexible job shop scheduling with blockages [...] |

Stougie | Scheduling with job-splitting and fixed setup [...] |

Steiner | Scheduling and the traveling salesman problem on permuted monge matrices [...] |

**13:15 - 14:45, room: H 3013**

**Chair: Arie Koster**

Recoverable robust combinatorial optimization

Büsing | *k*-distance recoverable robustness [...] |

Koster | The recoverable robust knapsack problem [...] |

**13:15 - 14:45, room: H 3021**

**Chair: Vincenzo Bonifaci**

Scheduling algorithms II

Rutten | Scheduling sporadic tasks on unrelated parallel machines [...] |

Wiese | A new approach to online scheduling: Approximating the optimal competitive ratio [...] |

Megow | Nearly optimal universal solutions for knapsack and sequencing on an unreliable machine [...] |

**15:15 - 16:45, room: H 3004**

**Chair: Neil Olver**

Interactions between optimization and game theory in scheduling

Uetz | Mechanism design for single machine scheduling by ILP [...] |

Hoeksma | Price of anarchy for minsum related machine scheduling [...] |

Olver | Approximation algorithms for scheduling via coordination mechanisms [...] |

**15:15 - 16:45, room: H 3005**

**Chair: Frédéric Meunier**

Exact and approximation algorithms on graphs

Cornaz | Strengthening Lovász bound for coloring with a new graph transformation [...] |

Meunier | A routing problem raised by self-service bike hiring systems [...] |

Bruhn | Clique or hole in claw-free graphs [...] |

**15:15 - 16:45, room: H 3008**

**Chair: Christian Wulff-Nilsen and Glencora Borradaile**

Distances in graphs

Agarwal | The space-stretch-time tradeoff in distance oracles [...] |

Wulff-Nilsen | Approximate distance oracles with improved preprocessing and query time [...] |

Roditty | A survey on distance oracles [...] |

**15:15 - 16:45, room: H 3012**

**Chair: Alexander Tesch**

Scheduling II

Oster | A branch and cut algorithm for solving capacitated max *k*-cut with an application in scheduling [...] |

Tesch | Optimization of the ISMP 2012 schedule [...] |

**15:15 - 16:45, room: H 3013**

**Chair: Peter Gritzmann**

Constrained clustering

Borgwardt | On the diameter of partition polytopes and vertex-disjoint cycle cover [...] |

Shakhshshneyder | Hardness and non-approximability of constrained clustering [...] |

Brieden | Constrained clustering with convex objective function [...] |

**15:15 - 16:45, room: H 3021**

**Chair: Britta Peis**

Equilibria and combinatorial structures

Kern | Cooperative games and fractional programming [...] |

Király | Multiplayer multicommodity flows [...] |

McCormick | A primal-dual algorithm for weighted abstract cut packing [...] |

#### Tuesday

**10:30 - 12:00, room: H 3004**

**Chair: Stefano Gualandi**

Generalizing shortest paths, cycles, and Steiner trees

Gualandi | Resource constrained shortest paths with a super additive objective function [...] |

Dan | Finding the shortest cycle in directed graphs under some constraints on passing vertices and paths [...] |

Karbstein | Approximation and min-max results for the Steiner connectivity problem [...] |

**10:30 - 12:00, room: H 3005**

**Chair: Jon Lee**

Submodularity and covering

Sviridenko | New and improved bounds for the minimum set cover problem [...] |

Krause | Adaptive submodularity: Theory and applications in active learning and stochastic optimization [...] |

Zenklusen | Matroids and integrality gaps for hypergraphic Steiner tree relaxations [...] |

**10:30 - 12:00, room: H 3008**

**Chair: Viswanath Nagarajan**

LP based approximation algorithms for location and routing

Byrka | Fault-tolerant facility location: A randomized dependent LP-rounding algorithm [...] |

Blasiak | Improved approximation algorithms for the minimum latency problem via prize-collecting paths [...] |

Friggstad | A logarithmic approximation for the directed latency problem [...] |

**10:30 - 12:00, room: H 3012**

**Chair: Sandro Bosio**

Scheduling III

Poppenborg | Modeling the resource-constrained project scheduling problem with resource transfers using a graph approach. [...] |

Bosio | Mailroom production planning [...] |

**10:30 - 12:00, room: H 3013**

**Chair: Winfried Hochstättler**

Trees and words

Hochstättler | Some heuristics for the binary paint shop problem and their expected number of colour changes [...] |

Krzywkowski | An algorithm listing all minimal dominating sets of a tree [...] |

Matsui | An enumeration algorithm for the optimal cost vertex-colorings for trees [...] |

**10:30 - 12:00, room: H 3021**

**Chair: Tim Nieberg**

Data structures and algorithms for VLSI routing

Müller | Multi-flows and generalizations in VLSI routing [...] |

Schulte | Efficient algorithms and data structures in VLSI detailed routing [...] |

Gester | New challenges in chip design driven by technology scaling [...] |

**13:15 - 14:45, room: H 3004**

**Chair: Pablo A. Parrilo and Rekha Thomas**

Cone factorizations and lifts of convex sets

Vavasis | Identifying *k* large submatrices using convex programming [...] |

Gouveia | Semidefinite lifts of polytopes [...] |

Glineur | Compact polyhedral approximations for convex sets defined by polynomials [...] |

**13:15 - 14:45, room: H 3005**

**Chair: Konstantinos Georgiou**

Lift-and-project methods for combinatorial optimization problems

Chlamtac | Reduced integrality gaps and improved approximations via lift-and-project methods [...] |

Laurent | Error bounds for sums of squares relaxations of some polynomial optimization problems [...] |

Tulsiani | Effectiveness and limitations of local constraints [...] |

**13:15 - 14:45, room: H 3008**

**Chair: Antoine Deza and Jesus Antonio De Loera**

Combinatorics and geometry of linear optimization I

Santos | Counter-examples to the Hirsch conjecture [...] |

Hähnle | An abstract view on the polynomial Hirsch conjecture [...] |

Zinchenko | Polytopes and arrangements: Diameter and curvature [...] |

**13:15 - 14:45, room: H 3012**

**Chair: Stefan Hougardy**

Algorithms for transistor-level layout

Hougardy | Transistor level layout: Algorithms and complexity [...] |

Schneider | BonnCell: Placement of leaf cells in VLSI design [...] |

Nieberg | BonnCell: Routing of leaf cells in VLSI design [...] |

**13:15 - 14:45, room: H 3013**

**Chair: Gyula Pap**

Matching and related problems

Bérczi | Restricted *b*-matchings [...] |

Takazawa | Covering cuts in bridgeless cubic graphs [...] |

Hartvigsen | A generalized *k*-matching problem [...] |

**13:15 - 14:45, room: H 3021**

**Chair: Alantha Newman**

Sampling, sorting and graph traversal: Algorithms for finding permutations

Miracle | Mixing times of self-organizing lists and biased permutations [...] |

Paluch | Simpler approximation of the maximum asymmetric traveling salesman problem [...] |

**15:15 - 16:45, room: H 3004**

**Chair: Samuel Fiorini and Gautier Stauffer**

Extended formulations in discrete optimization I

Pokutta | On linear programming formulations of the TSP polytope [...] |

Rothvoss | Some 0/1 polytopes need exponential size extended formulations [...] |

Grappe | Extended formulations, non-negative factorizations, and randomized communication protocols [...] |

**15:15 - 16:45, room: H 3005**

**Chair: Tamás Király**

Matroid parity

Cheung | Algebraic algorithms for linear matroid parity problems [...] |

Iwata | Weighted linear matroid parity [...] |

Pap | Weighted linear matroid parity - A primal-dual approach [...] |

**15:15 - 16:45, room: H 3008**

**Chair: Jesus Antonio De Loera and Antoine Deza**

Combinatorics and geometry of linear optimization II

Pataki | Bad semidefinite programs: They all look the same [...] |

Stephen | The width of 4-prismatoids [...] |

Bremner | Minimum norm points on the boundary of convex polytopes [...] |

**15:15 - 16:45, room: H 3012**

**Chair: Dorit S. Hochbaum**

LP relaxations

Godinho | On a time-dependent formulation for the travelling salesman problem [...] |

Hochbaum | Flow-based algorithms that solve clustering problems related to graph expander, normalized cut and conductance better than the spectral method [...] |

Kuo | On the mixed set covering, partitioning and packing problem [...] |

**15:15 - 16:45, room: H 3013**

**Chair: Neil Olver and Jose Correa**

Combinatorial optimization and equilibria for flows over time

Fleischer | Competitive strategies for routing flow over time [...] |

Larre | Existence and uniqueness of equilibria for flows over time [...] |

Koch | Continuous and discrete flows over time [...] |

**15:15 - 16:45, room: H 3021**

**Chair: Andreas S. Schulz**

New insights for old problems

Stauffer | A simple and fast 2-approximation algorithm for the one-warehouse multi-retailer problem [...] |

Segev | An approximate dynamic-programming approach to the joint replenishment problem [...] |

Schulz | The joint replenishment problem and the problem of clustering frequency-constrained maintenance jobs are integer-factorization hard [...] |

#### Wednesday

**10:30 - 12:00, room: H 3004**

**Chair: Gautier Stauffer and Volker Kaibel**

Extended formulations in discrete optimization II

Van Vyve | Projecting an extended formulation [...] |

Pashkovich | Constructing extended formulations using polyhedral relations [...] |

Theis | Some lower bounds on sizes of positive semidefinite extended formulations [...] |

**10:30 - 12:00, room: H 3005**

**Chair: Klaus Truemper**

Algorithm for matrices and matroids

Walter | A simple algorithm for testing total unimodularity of matrices [...] |

Pitsoulis | Decomposition of binary signed-graphic matroids [...] |

**10:30 - 12:00, room: H 3008**

**Chair: Jesus Antonio De Loera and Antoine Deza**

Combinatorics and geometry of linear optimization III

Mizuno | An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables [...] |

Adler | The equivalence of linear programs and zero-sum games [...] |

Zwick | Subexponential lower bounds for randomized pivoting rules for the simplex algorithm [...] |

**10:30 - 12:00, room: H 3012**

**Chair: Shunji Umetani**

Heuristics I

Badri | A divide-and-bridge heuristic for Steiner minimal trees on the Euclidean plane [...] |

Umetani | A heuristic algorithm for the set multicover problem with generalized upper bound constraints [...] |

**10:30 - 12:00, room: H 3013**

**Chair: Chandra Chekuri**

Network flows

Afsharirad | Maximum dynamic flow interdiction problem [...] |

Karrenbauer | Planar min-cost flow in nearly *O(n*^{3/2}) [...] |

Chekuri | Multicommodity flows and cuts in polymatroidal networks [...] |

**10:30 - 12:00, room: H 3021**

**Chair: Peter Sanders**

Routing for public transportation

Müller-Hannemann | Coping with delays: Online timetable information and passenger-oriented train disposition [...] |

Pajor | Round-based public transit routing [...] |

Bast | Next-generation route planning: Multi-modal, real-time, personalized [...] |

**13:15 - 14:45, room: H 3004**

**Chair: Volker Kaibel and Samuel Fiorini**

Extended formulations in discrete optimization III

Tiwary | Extended formulations for polygon [...] |

Conforti | Extended formulations in mixed-integer programming [...] |

Zambelli | Mixed-integer bipartite vertex covers and mixing sets [...] |

**13:15 - 14:45, room: H 3005**

**Chair: Maurice Queyranne**

Geometric combinatorial optimization

Queyranne | Modeling convex subsets of points [...] |

Dragoti-Cela | On the x-and-y axes travelling salesman problem [...] |

**13:15 - 14:45, room: H 3008**

**Chair: Friedrich Eisenbrand**

Combinatorics and geometry of linear optimization IV

Gärtner | Abstract optimization problems revisited [...] |

Di Summa | A new bound on the diameter of polyhedra [...] |

Kim | Subset partition graphs and an approach to the linear Hirsch conjecture [...] |

**13:15 - 14:45, room: H 3012**

**Chair: Abderrezak Mohamed Djadoun**

Heuristics II

Bouamama | A population-based iterated greedy algorithm for the minimum weight vertex cover problem [...] |

Djadoun | Random synchronized prospecting: A new metaheuristic for combinatorial optimization [...] |

**13:15 - 14:45, room: H 3013**

**Chair: Geir Dahl**

Assignment problems

Dahl | Generalized Birkhoff polytopes and majorization [...] |

Heismann | The hypergraph assignment problem [...] |

**13:15 - 14:45, room: H 3021**

**Chair: Renato Werneck**

Graph partitioning and clustering

Werneck | Exact combinatorial branch-and-bound for graph bisection [...] |

Christian | High quality graph partitioning [...] |

Meyerhenke | Current trends in graph clustering [...] |

**15:15 - 16:45, room: H 3004**

**Chair: Alantha Newman**

Knapsack and bin packing

Newman | A counterexample to Beck's three permutations conjecture [...] |

Detti | The bounded sequential multiple knapsack problem [...] |

Schauer | Knapsack problems with disjunctive constraints [...] |

**15:15 - 16:45, room: H 3005**

**Chair: Jakub Marecek**

Graph coloring

Sukegawa | Lagrangian relaxation and pegging test for clique partitioning problems [...] |

Jurkiewicz | Colorings of the strong product of graphs [...] |

Marecek | Semidefinite programming relaxations in timetabling and matrix-free implementations of augmented Lagrangian methods for solving them [...] |

**15:15 - 16:45, room: H 3008**

**Chair: Yury Kochetov**

Competitive and multi-objective facility location

Beresnev | Algorithms for discrete competitive facility location problem [...] |

Kochetov | A local search algorithm for the (r | p)-centroid problem on the plane [...] |

Pascoal | Path based method for multicriteria metro location [...] |

**15:15 - 16:45, room: H 3012**

**Chair: Beyzanur Cayir**

Heuristics III

Kononova | Local search heuristic for the buffer-constrained two-stage multimedia scheduling problem [...] |

Cayir | A genetic algorithm for truck to door assignment in warehouses [...] |

**15:15 - 16:45, room: H 3013**

**Chair: Shungo Koichi**

Polyhedra in combinatorial optimization

Koichi | A note on ternary semimodular polyhedra [...] |

Maksimenko | The common face of some 0/1 polytopes with NP-complete nonadjacency relations [...] |

Li | The polyhedral relationship between the capacitated facility location polytope and its knapsack and single-node flow relaxations [...] |

**15:15 - 16:45, room: H 3021**

**Chair: Andrew Goldberg**

Routing in road networks

Sanders | Advance route planning using contraction hierarchies [...] |

Goldberg | The hub labeling algorithm [...] |

Delling | Realistic route planning in road networks [...] |

#### Thursday

**10:30 - 12:00, room: H 3004**

**Chair: Jaroslav Nesetril and Martin Loebl**

Optimization and enumeration

Ossona de Mendez | Large structured induced subgraphs with close homomorphism statistics [...] |

Chertkov | Computing the permanent with belief propagation [...] |

Coja-Oghlan | Catching the k-NAESAT threshold [...] |

**10:30 - 12:00, room: H 3005**

**Chair: Michael Juenger**

Robust network design

Kutschka | Robust metric inequalities for network design under demand uncertainty [...] |

Schmidt | Single commodity robust network design: Models and algorithms [...] |

Sanità | Steiner tree approximation via iterative randomized rounding [...] |

**10:30 - 12:00, room: H 3008**

**Chair: David S. Johnson**

Resource placement in networks

Johnson | Disjoint path facility location: Theory and practice [...] |

Applegate | Using an exponential potential function method to optimize video-on-demand content placement [...] |

**10:30 - 12:00, room: H 3012**

**Chair: Réal André Carbonneau**

Exact algorithms for hard problems

Carbonneau | Globally optimal clusterwise regression by branch and bound optimization with heuristics, sequencing and ending subset [...] |

Fügenschuh | LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: A computational comparison [...] |

Cerveira | A two-stage branch and bound algorithm to solve truss topology design problems [...] |

**10:30 - 12:00, room: H 3013**

**Chair: Ralf Borndörfer**

Combinatorial optimization in railways II

Hansmann | Minimal shunting operations for freight train composition [...] |

Bärmann | Approximate robust optimization and applications in railway network expansion [...] |

Klug | An approach for solving the freight train routing problem [...] |

**10:30 - 12:00, room: H 3021**

**Chair: Alantha Newman and Heiko Röglin**

Smoothed analysis of algorithms

Brunsch | Improved smoothed analysis of multiobjective optimization [...] |

Plociennik | A probabilistic PTAS for shortest common superstring [...] |

**13:15 - 14:45, room: H 3004**

**Chair: Peter Recht**

Cycles in graphs

Recht | A "min-max-theorem'' for the cycle packing problem in Eulerian graphs [...] |

Sprengel | An optimal cycle packing for generalized Petersen graphs *P(n,k)* with *k* even [...] |

Aoudia | 4-cycle polytope on a graph [...] |

**13:15 - 14:45, room: H 3005**

**Chair: Antonio Mucherino and Nelson Maculan**

Distance geometry and applications

Lavor | A discrete approach for solving distance geometry problems related to protein structure [...] |

Nucci | Solving the discretizable molecular distance geometry problem by multiple realization trees [...] |

Kim | Molecular distance geometry problem: A perspective from the Voronoi diagram [...] |

**13:15 - 14:45, room: H 3008**

**Chair: Satoru Fujishige**

Discrete structures and algorithms II

Shioura | Computing the convex closure of discrete convex functions [...] |

Kamiyama | Matroid intersection with priority constraints [...] |

Peis | Resource buying games [...] |

**13:15 - 14:45, room: H 3012**

**Chair: Laura Klein**

Nonlinear combinatorial optimization

Klein | Separation algorithms for quadratic combinatorial optimization problems [...] |

Gorge | Quadratic cuts for semidefinite relaxation of combinatorial problems [...] |

Vidal | A new proposal for a lower bound in a generalized quadratic assignment problem applied to the zoning problem [...] |

**13:15 - 14:45, room: H 3013**

**Chair: Peter Gritzmann**

Inverse problems

Catanzaro | An exact algorithm to reconstruct phylogenetic trees under the minimum evolution criterion [...] |

Gritzmann | On some discrete inverse problems: Combinatorial optimization in discrete and refraction tomography [...] |

**13:15 - 14:45, room: H 3021**

**Chair: Bo Chen**

Combinatorial optimization under uncertainty

Chao | Dynamic pricing decision for a monopoly with strategic customers and price adjustment [...] |

Noorizadegan | A branch and cut approach for some heterogeneous routing problems under demand uncertainty [...] |

Zheng | Least square regret in stochastic discrete optimization [...] |

**15:15 - 16:45, room: H 3004**

**Chair: Sándor P. Fekete and Alexander Kröller**

Optimization methods for geometric problems

Halperin | Multi-objective path optimization in motion planning: From the particular to the general [...] |

de Souza | Towards solving to optimality the art gallery with point-guards problem [...] |

Kröller | Practical solutions and bounds for art gallery problems [...] |

**15:15 - 16:45, room: H 3005**

**Chair: Piotr Sankowski**

Recent advances in matching algorithms

Gupta | Fully dynamic maximal matching in *O(**log* n) update time [...] |

Huang | Efficient algorithms for maximum weight matchings in general graphs with small edge weights [...] |

Mahdian | Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs [...] |

**15:15 - 16:45, room: H 3008**

**Chair: Satoru Fujishige**

Discrete structures and algorithms III

Kobayashi | An algorithm for finding a maximum *t*-matching excluding complete partite subgraphs [...] |

Tanigawa | Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries [...] |

Nagano | Size-constrained submodular minimization through minimum norm base [...] |

**15:15 - 16:45, room: H 3012**

**Chair: Attila Bernáth**

Arborescences

Bernáth | Covering minimum cost arborescences [...] |

Leston-Rey | Packing entering sets in kernel systems [...] |

Call | A polyhedral analysis of a unique shortest path routing polytope [...] |

**15:15 - 16:45, room: H 3013**

**Chair: Martin Skutella**

Scheduling and network flows over time

Marchetti-Spaccamela | Universal sequencing on an unreliable machine [...] |

Groß | Approximating earliest arrival flows in arbitrary networks [...] |

Kappmeier | Flows over time with negative transit times and arc release dates [...] |

#### Friday

**10:30 - 12:00, room: H 3004**

**Chair: Guochuan Zhang**

Approximation algorithms for hard problems

Chen | Approximation algorithms for scheduling parallel machines with capacity constraints [...] |

Chen | Approximation algorithms for parallel open shop scheduling [...] |

Hu | New models for network connection problems with interval data [...] |

**10:30 - 12:00, room: H 3005**

**Chair: Erwin Pesch**

Combinatorial optimization in logistics

Schulz | Explanation algorithms in cumulative scheduling [...] |

Nossack | Benders decomposition for a 1-full-truckload pickup-and-delivery vehicle routing problem [...] |

Pesch | A branch-and-bound algorithm for the acyclic partitioning problem [...] |

**10:30 - 12:00, room: H 3008**

**Chair: Gautier Stauffer**

Algorithms in claw-free graphs

van Leeuwen | Domination when the stars are out - Efficient decomposition of claw-free graphs [...] |

Faenza | Separating stable sets in claw-free graphs through extended formulations [...] |

Nobili | A decomposition algorithm for the weighted stable-set problem in claw-free graphs [...] |

**10:30 - 12:00, room: H 3012**

**Chair: Claudia Snels**

Cliques, stable sets, and perfect graphs

Montenegro | On the *N*-index of the stable set polytope related to antiwebs [...] |

Snels | Minimum weighted clique cover on strip-composed perfect graphs [...] |

**10:30 - 12:00, room: H 3013**

**Chair: Ralf Borndörfer**

Extended formulations

Serafini | Compact formulations for large-scale LP problems [...] |

Hildenbrandt | An extended formulation for the target visitation problem [...] |

Borndörfer | Configuration models for solving integrated combinatorial optimization problems [...] |

**13:15 - 14:45, room: H 3004**

**Chair: Annegret K. Wagler**

Packing, covering and domination I

Wagler | Generalized row family inequalities for the set covering polyhedron [...] |

Argiroffo | The identifying code polyhedron of cycles [...] |

Valicov | Complexity of identifying codes in some subclasses of perfect graphs [...] |

**13:15 - 14:45, room: H 3005**

**Chair: Adam Nicholas Letchford**

Nonlinear combinatorial optimisation problems I

Baumann | Exact algorithms for combinatorial optimization problems with submodular objective functions [...] |

Liers | A polyhedral approach to the quadratic matching problem [...] |

Narayanan | Some properties of integer hulls of convex sets [...] |

**13:15 - 14:45, room: H 3013**

**Chair: Jarosław Byrka**

Facility location

Rybicki | Improved LP-rounding approximation algorithm for *k*-level uncapacitated facility location [...] |

Ahmadian | Improved approximation guarantees for lower-bounded facility location [...] |

**15:15 - 16:45, room: H 3004**

**Chair: Annegret K. Wagler**

Packing, covering and domination II

Pecher | On the theta number of powers of cycle graphs [...] |

Bianchi | The disjunctive rank of the stable set polytope of web graphs [...] |

Torres | On the Chvátal-closure of the fractional set covering polyhedron of circulant matrices [...] |

**15:15 - 16:45, room: H 3005**

**Chair: Christoph Buchheim**

Nonlinear combinatorial optimization problems II

Djeumou Fomeni | A dynamic programming heuristic for the quadratic knapsack problem [...] |

Hübner | Ellipsoid bounds for convex quadratic integer programming [...] |

Elloumi | A unified view of linear and quadratic convex reformulation for binary quadratic programming [...] |

**15:15 - 16:45, room: H 3008**

**Chair: James Orlin and Laszlo Végh**

Faster algorithms for network flow problems

Nussbaum | Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time [...] |

Végh | Concave generalized flows with applications to market equilibria [...] |

**15:15 - 16:45, room: H 3012**

**Chair: Anand Srivastav**

Graph optimization problems in the streaming model

Konrad | On the order of graph streams [...] |

Kliemann | *(1+1/k)*-Approximate maximum matching in bipartite graph streams in *O(k*^{5}) passes and improvements [...] |

Zelke | Algorithmic techniques for data stream computations [...] |

**15:15 - 16:45, room: H 3013**

**Chair: Nicholas Harvey**

Flows, cuts, and sparsifiers

Harvey | Graph sparsifiers [...] |

Kelner | Electrical flows, linear systems, and faster approximations of maximum flows, minimum *s*-*t* cuts, and multicommodity flows in undirected graphs [...] |

Weibel | When the cut condition is enough: Characterization of multiflow problems by forbidden minors [...] |