Logo - springer
Slogan - springer

Computer Science - Theoretical Computer Science | Integer Programming and Combinatorial Optimization - 11th International IPCO Conference, Berlin,

Integer Programming and Combinatorial Optimization

11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings

Jünger, Michael, Kaibel, Volker (Eds.)

2005, XI, 484 p. Also available online.

Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-3-540-32102-6

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-3-540-26199-5

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

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.

Content Level » Research

Keywords » algorithm - algorithmics - algorithms - approximation algorithms - calculus - combinatorial optimization - combinatorics - computational complexity - computational discrete Mathematics - computational geometry - graph computations - integer programming - network algorithms - optimization - programming

Related subjects » Image Processing - Theoretical Computer Science

Table of 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.

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Discrete Mathematics in Computer Science.