Integer Programming and Combinatorial Optimization : 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010, Proceedings / edited by Friedrich Eisenbrand, Bruce Shepherd.

Format:

Book

Contributor:

Eisenbrand, Friedrich, editor.

Shepherd, F. Bruce (Frederick Bruce), editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

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

Theoretical Computer Science and General Issues ; 6080

Language:

English

Subjects (All):

Algorithms.

Computer science--Mathematics.

Computer science.

Computer graphics.

Data structures (Computer science).

Numerical analysis.

Computer networks.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Computer Graphics.

Data Structures.

Numeric Computing.

Computer Communication Networks.

Local Subjects:

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Computer Graphics.

Data Structures.

Numeric Computing.

Computer Communication Networks.

Physical Description:

1 online resource (XIII, 466 pages) : 45 illustrations.

Edition:

First edition 2010.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2010.

System Details:

text file PDF

Summary:

Theidea ofa refereedconferencefor the mathematicalprogrammingcommunity was proposed by Ravi Kannan and William Pulleyblank to the Mathematical Programming Society (MPS) in the late 1980s. Thus IPCO was born, and MPS has sponsored the conference as one of its main events since IPCO I at the University of Waterloo in 1990. The conference has become the main forum for recent results in Integer Programming and Combinatorial Optimization in the non-Symposium years. This volume compiles the papers presented at IPCO XIV held June 9-11, 2010, at EPFL in Lausanne. The scope of papers considered for IPCO XIV is likely broader than at IPCO I. This is sometimes due to the wealth of new questions and directions brought from related areas. It can also be due to the successful application of "math programming" techniques to models not tra- tionally considered. In any case, the interest in IPCO is greater than ever and this is re?ected in both the number (135) and quality of the submissions. The ProgrammeCommittee with 13 memberswasalsoIPCO'slargest. We thankthe members of the committee, as well as their sub-reviewers, for their exceptional (and time-consuming) work and especially during the online committee meeting held over January. The process resulted in the selection of 34 excellent research papers which were presented in non-parallel sessions over three days in L- sanne. Unavoidably, this has meant that many excellent submissions were not able to be included.

Contents:

Solving LP Relaxations of Large-Scale Precedence Constrained Problems

Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings

Eigenvalue Techniques for Convex Objective, Nonconvex Optimization Problems

Restricted b-Matchings in Degree-Bounded Graphs

Zero-Coefficient Cuts

Prize-Collecting Steiner Network Problems

On Lifting Integer Variables in Minimal Inequalities

Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities

On Generalizations of Network Design Problems with Degree Bounds

A Polyhedral Study of the Mixed Integer Cut

Symmetry Matters for the Sizes of Extended Formulations

A 3-Approximation for Facility Location with Uniform Capacities

Secretary Problems via Linear Programming

Branched Polyhedral Systems

Hitting Diamonds and Growing Cacti

Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems

A Polynomial-Time Algorithm for Optimizing over N-Fold 4-Block Decomposable Integer Programs

Universal Sequencing on a Single Machine

Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm

Integer Quadratic Quasi-polyhedra

An Integer Programming and Decomposition Approach to General Chance-Constrained Mathematical Programs

An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming

Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain

The Price of Collusion in Series-Parallel Networks

The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron

A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information

On Column-Restricted and Priority Covering Integer Programs

On k-Column Sparse Packing Programs

Hypergraphic LP Relaxations for Steiner Trees

Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs

Efficient Algorithms for Average Completion Time Scheduling

Experiments with Two Row Tableau Cuts

An OPT?+?1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths

On the Rank of Cutting-Plane Proof Systems.

Other Format:

Printed edition:

ISBN:

978-3-642-13036-6

9783642130366

Access Restriction:

Restricted for use by site license.