Integer Programming and Combinatorial Optimization

by Cook, William J.; Schulz, Andreas S.

• ISBN13: 9783540436768
• ISBN10: 3540436766
• Format: Paperback
• Copyright: 2002-05-01
• Publisher: Springer Verlag

Summary

This research monograph deals with the study of wave phenomena caused by winds in the world's oceans. Particular attention is paid to modern developments that take into account the propagation of ocean waves at global distances and their interaction with the sea bottom, ocean currents and the ice cover. With this book the author provides the first methodical presentation of the generation, evolution and propagation of wind-induced ocean waves.

Table of Contents

A Faster Scaling Algorithm for Minimizing Submodular Functions	p. 1
A Generalization of EdmondsÆ Matching and Matroid Intersection Algorithms	p. 9
A Coordinatewise Domain Scaling Algorithm for M-convex Function Minimization	p. 21
The Quickest Multicommodity Flow Problem	p. 36
A New Min-Cut Max-Flow Ratio for Multicommodity Flows	p. 54
Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems	p. 67
Finding the Exact Integrality Gap for Small Traveling Salesman Problems	p. 83
Polynomial-Time Separation of Simple Comb Inequalities	p. 93
A New Approach to Cactus Construction Applied to TSP Support Graphs	p. 109
Split Closure and Intersection Cuts	p. 127
An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs	p. 145
Lifted Inequalities for 0-1 Mixed Integer Programming: Basic Theory and Algorithms	p. 161
On a Lemma of Scarf	p. 176
A Short Proof of SeymourÆs Characterization of the Matroids with the Max-Flow Min-Cut Property	p. 188
Integer Programming and Arrovian Social Welfare Functions	p. 194
Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design	p. 212
The Minimum Latency Problem Is NP-Hard for Weighted Trees	p. 230
An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem	p. 240
A Polyhedral Approach to Surface Reconstruction from Planar Contours	p. 258
The Semidefinite Relaxation of the k-Partition Polytope Is Strong	p. 273
A Polyhedral Study of the Cardinality Constrained Knapsack Problem	p. 291
A PTAS for Minimizing Total Completion Time of Bounded Batch Scheduling	p. 304
An Approximation Scheme for the Two-Stage, Two-Dimensional Bin Packing Problem	p. 315
On Preemptive Resource Constrained Scheduling: Polynomial-Time Approximation Schemes	p. 329
Hard Equality Constrained Integer Knapsacks	p. 350
The Distribution of Values in the Quadratic Assignment Problem	p. 367
A New Subadditive Approach to Integer Programming	p. 384
Improved Approximation Algorithms for Resource Allocation	p. 401
Approximating the Advertisement Placement Problem	p. 415
Algorithms for Minimizing Response Time in Broadcast Scheduling	p. 425
Building Edge-Failure Resilient Networks	p. 439
The Demand Matching Problem	p. 457
The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap	p. 475
Author Index	p. 487
Table of Contents provided by Publisher. All Rights Reserved.