Integer Programming and Combinatorial Optimization: 11th International Ipco Conference, Berlin, Germany, June 8-10, 2005, Proceedings

ISBN-13: 9783540261995 / Angielski / Miękka / 2005 / 488 str.

M. Junger; Michael Jnger; Volker Kaibel

Opis

Contains 34 papers, reviewed and selected from 119 submissions. This book addresses topics like mixed-integer programming, graph theory, graph algorithms, approximation, linear programming, approximability, packing, scheduling, computational geometry, randomization, network algorithms, sequencing, TSP, and the travelling salesman problem.

Spis treści

Mixed-Integer Cuts from Cyclic Groups.- Optimizing over the First Chvàtal Closure.- Sequential Pairing of Mixed Integer Inequalities.- Approximate Min-max Relations for Odd Cycles in Planar Graphs.- Disjoint Cycles: Integrality Gap, Hardness, and Approximation.- A Combinatorial Algorithm to Find a Maximum Even Factor.- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems.- On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem.- Inventory and Facility Location Models with Market Selection.- On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations.- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials.- Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring.- On the Inefficiency of Equilibria in Congestion Games.- Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times.- LP-Based Online Scheduling: From Single to Parallel Machines.- Unique Sink Orientations of Grids.- Jumping Doesn’t Help in Abstract Cubes.- Computing the Inertia from Sign Patterns.- Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem.- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem.- Smoothed Analysis of Integer Programming.- Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs.- Approximation Algorithms for Stochastic Inventory Control Models.- On Two-Stage Stochastic Minimum Spanning Trees.- Combinatorial Analysis of Generic Matrix Pencils.- Power Optimization for Connectivity Problems.- Packing Steiner Forests.- Bidimensional Packing by Bilinear Programming.- On the L ???-Norm of Extreme Points for Crossing Supermodular Directed Network LPs.- Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks.- Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem.- Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems.- A Study of Domino-Parity and k-Parity Constraints for the TSP.- Not Every GTSP Facet Induces an STSP Facet.

O autorze

Privatdozent Dr. med. Michael Jünger ist Oberarzt an der Abteilung für Dermatologie an der Universitäts-Hautklinik in Tübingen, Mitbegründer der Gefäßsportgruppe und Mitglied im Tübinger Arbeitskreis für Gefäßerkrankungen e. V.