Integer Programming and Combinatorial Optimization: 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings (Lecture Notes in Computer Science, 1610, Band 1610) - Softcover

Woeginger, Gerhard J.; Burkard, Rainer E.; Cornuejols, Gerard

Softcover

ISBN 10: 3540660194 ISBN 13: 9783540660194

Verlag: Springer, 2008

Inhaltsangabe

Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances.- Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts.- Solving the Convex Cost Integer Dual Network Flow Problem.- Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem.- Valid Inequalities for Problems with Additive Variable Upper Bounds.- A Min-Max Theorem on Feedback Vertex Sets (Preliminary Version).- On the Separation of Maximally Violated mod-k Cuts.- Improved Approximation Algorithms for Capacitated Facility Location Problems.- Optimal 3-Terminal Cuts and Linear Programming.- Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem.- Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube.- Universally Maximum Flow with Piecewise-Constant Capacities.- Critical Extreme Points of the 2-Edge Connected Spannning Subgraph Polytope.- An Orientation Theorem with Parity Conditions.- Parity Constrained k-Edge-Connected Orientations.- Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs.- On the Chvátal Rank of Certain Inequalities.- The Square-Free 2-Factor Problem in Bipartite Graphs.- The m-Cost ATSP.- A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem.- Edge-Splitting Problems with Demands.- Integral Polyhedra Associated with Certain Submodular Functions Defined on 012-Vectors.- Optimal Compaction of Orthogonal Grid Drawings (Extended Abstract).- On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms.- Experimental Evaluation of Approximation Algorithms for Single-Source Unsplittable Flow.- Approximation Algorithms for a Directed Network Design Problem.- Optimizing over AllCombinatorial Embeddings of a Planar Graph (Extended Abstract).- A Fast Algorithm for Computing Minimum 3-Way and 4-Way Cuts.- Scheduling Two Machines with Release Times.- An Introduction to Empty Lattice Simplices.- On Optimal Ear-Decompositions of Graphs.- Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications (Extended Abstract).- Vertex-Disjoint Packing of Two Steiner Trees: Polyhedra and Branch-and-Cut.

Details zur Ausgabe

• Verlag: Springer
• Erscheinungsdatum: 2008
• Sprache: Englisch
• ISBN 10: 3540660194
• ISBN 13: 9783540660194
• Einband: Taschenbuch
• Anzahl der Seiten: 472
• Kontakt zum Hersteller: Springer Nature Customer Service Center GmbH; ProductSafety@springernature.com; ; Europaplatz 3; Heidelberg; 69115; Deutschland