Scientific Program Cluster Details

Program -> Parallel Sessions -> Cluster List -> Details all clusters
Search talks included | sessions only


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(n3/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(k5) 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 [...]

 

 

Program -> Parallel Sessions -> Cluster List -> Details all clusters
Search talks included | sessions only
  Payday Loans In Missouri. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.