𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

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

✍ Scribed by Matteo Fischetti, Cristiano Saturni (auth.), Michael Jünger, Volker Kaibel (eds.)


Publisher
Springer-Verlag Berlin Heidelberg
Year
2005
Tongue
English
Leaves
494
Series
Lecture Notes in Computer Science 3509 Theoretical Computer Science and General Issues
Edition
1
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


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.

✦ Table of Contents


Front Matter....Pages -
Mixed-Integer Cuts from Cyclic Groups....Pages 1-11
Optimizing over the First ChvΓ tal Closure....Pages 12-22
Sequential Pairing of Mixed Integer Inequalities....Pages 23-34
Approximate Min-max Relations for Odd Cycles in Planar Graphs....Pages 35-50
Disjoint Cycles: Integrality Gap, Hardness, and Approximation....Pages 51-65
A Combinatorial Algorithm to Find a Maximum Even Factor....Pages 66-80
Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems....Pages 81-96
On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem....Pages 97-110
Inventory and Facility Location Models with Market Selection....Pages 111-124
On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations....Pages 125-135
Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials....Pages 136-151
Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut Β and Graph Coloring....Pages 152-166
On the Inefficiency of Equilibria in Congestion Games....Pages 167-181
Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times....Pages 182-195
LP-Based Online Scheduling: From Single to Parallel Machines....Pages 196-209
Unique Sink Orientations of Grids....Pages 210-224
Jumping Doesn’t Help in Abstract Cubes....Pages 225-235
Computing the Inertia from Sign Patterns....Pages 236-248
Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem....Pages 249-264
On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem....Pages 265-275
Smoothed Analysis of Integer Programming....Pages 276-290
Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs....Pages 291-305
Approximation Algorithms for Stochastic Inventory Control Models....Pages 306-320
On Two-Stage Stochastic Minimum Spanning Trees....Pages 321-334
Combinatorial Analysis of Generic Matrix Pencils....Pages 335-348
Power Optimization for Connectivity Problems....Pages 349-361
Packing Steiner Forests....Pages 362-376
Bidimensional Packing by Bilinear Programming....Pages 377-391
On the L β€‰βˆžβ€‰ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs....Pages 392-406
Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks....Pages 407-421
Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem....Pages 422-436
Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems....Pages 437-451
A Study of Domino-Parity and k -Parity Constraints for the TSP....Pages 452-467
Not Every GTSP Facet Induces an STSP Facet....Pages 468-482
Back Matter....Pages -

✦ Subjects


Discrete Mathematics in Computer Science; Numeric Computing; Algorithm Analysis and Problem Complexity; Computer Graphics


πŸ“œ SIMILAR VOLUMES


Integer Programming and Combinatorial Op
✍ Matteo Fischetti, Cristiano Saturni (auth.), Michael JΓΌnger, Volker Kaibel (eds. πŸ“‚ Library πŸ“… 2005 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<p>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 elevent

Integer Programming and Combinatorial Op
✍ Daniel Bienstock (ed.), George Nemhauser (ed.) πŸ“‚ Library πŸ“… 2004 πŸ› Springer 🌐 English

<P>This book constitutes the refereed proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2004, held in New York City, USA in June 2004.</P><P>The 32 revised papers presented were carefully reviewed and selected from 109 submissions. Among the

Integer Programming and Combinatorial Op
✍ Daniel Bienstock (ed.), George Nemhauser (ed.) πŸ“‚ Library πŸ“… 2004 πŸ› Springer 🌐 English

<P>This book constitutes the refereed proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2004, held in New York City, USA in June 2004.</P><P>The 32 revised papers presented were carefully reviewed and selected from 109 submissions. Among the

Integer Programming and Combinatorial Op
✍ Aaron Archer (auth.), Karen Aardal, Bert Gerards (eds.) πŸ“‚ Library πŸ“… 2001 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<p>This volume contains the papers selected for presentation at IPCO VIII, the Eighth Conference on Integer Programming and Combinatorial Optimization, Utrecht, The Netherlands, 2001. This meeting isa forum for researchers and practitioners working on various aspects of integer programming and combi

Integer Programming and Combinatorial Op
✍ Aaron Archer (auth.), Karen Aardal, Bert Gerards (eds.) πŸ“‚ Library πŸ“… 2001 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<p>This volume contains the papers selected for presentation at IPCO VIII, the Eighth Conference on Integer Programming and Combinatorial Optimization, Utrecht, The Netherlands, 2001. This meeting isa forum for researchers and practitioners working on various aspects of integer programming and combi

Integer Programming and Combinatorial Op
✍ Jon Lee, Jens Vygen (eds.) πŸ“‚ Library πŸ“… 2014 πŸ› Springer International Publishing 🌐 English

<p>This book constitutes the refereed proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014, held in Bonn, Germany, in June 2014. The 34 full papers presented were carefully reviewed and selected from 143 submissions. The conference is a fo