Integer Programming and Combinatorial Optimization : 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings / edited by Michael Jünger, Volker Kaibel.

Format:

Book

Contributor:

Jünger, M. (Michael), editor.

Kaibel, Volker, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 3509.

Theoretical Computer Science and General Issues ; 3509

Language:

English

Subjects (All):

Computer science--Mathematics.

Computer science.

Numerical analysis.

Algorithms.

Computer graphics.

Discrete Mathematics in Computer Science.

Numeric Computing.

Algorithm Analysis and Problem Complexity.

Computer Graphics.

Local Subjects:

Discrete Mathematics in Computer Science.

Numeric Computing.

Algorithm Analysis and Problem Complexity.

Computer Graphics.

Physical Description:

1 online resource (XII, 488 pages).

Edition:

First edition 2005.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2005.

System Details:

text file PDF

Summary:

Since its start in 1990, the IPCO conference series (held under the auspices of theMathematicalProgrammingSociety)hasbecomeanimportantforumforthe presentation of recent results in Integer Programming and Combinatorial Op- mization. This volume compiles the papers presented at IPCO XI, the eleventh conference in this series, held June 8-10, 2005, at the Technische Universit ̈ at Berlin. The high interest in this conference series is evident in the large number of submissions. For IPCO XI, 119 extended abstracts of up to 10 pages were submitted. During its meeting on January 29-30, 2005, the Program Committee carefully selected 34 contributions for presentation in non-parallel sessions at the conference. The ?nal choices were not easy at all, since, due to the limited number of time slots, many very good papers could not be accepted. During the selection process the contributions were refereed according to the standards of refereed conferences. As a result of this procedure, you have in your hands a volume that contains papers describing high-quality research e?orts. The page limit for contributions to this proceedings volume was set to 15. You may ?nd full versions of the papers in scienti?c journals in the near future. We thank all the authors who submitted papers. Furthermore, the Program Committee is indebted to the many reviewers who, with their speci?c expertise, helped a lot in making the decisions.

Contents:

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.

Other Format:

Printed edition:

ISBN:

978-3-540-32102-6

9783540321026

Access Restriction:

Restricted for use by site license.