Integer Programming and Combinatorial Optimization: 6th International Ipco Conference Houston, Texas, June 22-24, 1998 Proceedings

ISBN-13: 9783540645900 / Angielski / Miękka / 1998 / 435 str.

R. E. Bixby; E. a. Boyd; R. Z. Rios-Mercado

Opis

This volume contains the papers selected for presentationat IPCO VI, the Sixth InternationalConferenceonInteger ProgrammingandCombinatorialOptimi- tion, held inHouston, Texas, USA, June22{24,1998.TheIPCOseriesofconf- ences highlights recent developments in theory, computation, and applications of integer programming and combinatorial optimization. These conferences are sponsoredby the Mathematical ProgrammingSociety, and are held in the years in which no International Symosium on Mathema- cal Programming takes place. Earlier IPCO conferences were held in Waterloo (Canada) in May 1990; Pittsburgh (USA) in May 1992; Erice (Italy) in April 1993; Copenhagen (Denmark) in May 1995; and Vancouver (Canada) in June 1996. The proceedings of IPCO IV (edited by Egon Balas and Jens Clausen in 1995) and IPCO V (edited by William Cunningham, Thomas McCormick, and Maurice Queyranne in 1996), were published by Springer-Verlag in the series Lecture Notes in Computer Science as Volumes 920 and 1084, respectively. The proceedings of the rst three IPCO conferences were published by organizing institutions. A total of77 extended abstracts, mostly of an excellentquality, wereinitially submitted. Following the IPCO policy of having only one stream of sessions over a three day span, the ProgramCommittee selected 32 papers. As a result, many outstanding papers could not be selected. The papers included in this volume have not been refereed. It is expected that revised versions of these works will appear in scienti c journals. The Program Committee thanks all the authors of submitted extended - stracts and papers for their support of the IPCO conferences.

Spis treści

0,1 Matrices, Matroids.- The Packing Property.- A Characterization of Weakly Bipartite Graphs.- Bipartite Designs.- Characterizing Noninteger Polyhedra with 0–1 Constraints.- A Theorem of Truemper.- The Generalized Stable Set Problem for Claw-Free Bidirected Graphs.- On a Min-max Theorem of Cacti.- Edge Connectivity.- Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs.- A New Bound for the 2-Edge Connected Subgraph Problem.- An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs.- Algorithms.- Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width.- Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs.- Approximation Algorithms for the Mixed Postman Problem.- Improved Approximation Algorithms for Uncapacitated Facility Location.- The Maximum Traveling Salesman Problem Under Polyhedral Norms.- Integer Programming Applications.- Polyhedral Combinatorics of Benzenoid Problems.- Consecutive Ones and a Betweenness Problem in Computational Biology.- Solving a Linear Diophantine Equation with Lower and Upper Bounds on the Variables.- Integer Programming Computation.- The Intersection of Knapsack Polyhedra and Extensions.- New Classes of Lower Bounds for Bin Packing Problems.- Solving Integer and Disjunctive Programs by Lift and Project.- A Class of Hard Small 0—1 Programs.- Network Flows.- Building Chain and Cactus Representations of All Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time.- Simple Generalized Maximum Flow Algorithms.- The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem.- An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow.- Scheduling.- Non-approximability Results for Scheduling Problems with Minsum Criteria.- Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems.- An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines.- On the Relationship Between Combinatorial and LP-Based Approaches to NP-Hard Scheduling Problems.- Quadratic Assignment Problems.- Polyhedral Combinatorics of Quadratic Assignment Problems with Less Objects than Locations.- Incorporating Inequality Constraints in the Spectral Bundle Method.