2001
2001: IPCO VIII in Utrecht, The Netherlands Program Committee: Karen Aardal, Utrecht University Imre Barany, Hungarian Academy of Sciences and University College London Dan Bienstock, Columbia University Michele Conforti, University of Padova Bert Gerards, PC chair, CWI Amsterdam Michel Goemans, Massachusetts Institute of Technology Monique Laurent, CWI Amsterdam and CNRS Gerhard J. Woeginger, TU Graz and Universiteit Twente List of accepted papers: A. Archer. Two O(log*k)-approximation algorithms for the asymmetric k-center problem. Y. Azar and O. Regev. Strongly polynomial algorithms for the unsplittable flow problem. J. Cheriyan and S. Vempala. Edge coverings of set-pairs. C.F. Chou, M. Queyranne and D. Simchi-Levi. The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. F.A. Chudak, T. Roughgarden and D.P. Williamson. Approximate k-MSTs and k-Steiner Trees via the primal-dual method and Lagrangean relaxation. G. Cornuejols and Y. Li. On the rank of mixed 0,1 polyhedra. F. Eisenbrand and G. Rote. Fast 2-Variable Integer Programming. M. Elkin and D. Peleg. Approximating k-spanner problems for k>2. T. Fleiner. A matroid-generalization of the stable matching polytope. L. Fleischer. A 2-approximation for (0,1,2) survivable network design. A. Frank and T. Kiraly. Combined connectivity augmentation and orientation problems. A. Frank and L. Szego. An extension of a theorem of Henneberg and Laman. S. Fujishige and S. Iwata. Bisubmodular function minimization. N. Garg, R. Khandekar, G. Konjevod, R. Ravi, F.S. Salman and A. Sinha. On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. B. Guenin. Circuit Mengerian directed graphs. B. Guenin. Integral polyhedra related to even cycle and even cut matroids. E. Halperin and U. Zwick. A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. R. Hassin and A. Levin. Synthesis of two-commodity flow networks. B. Jackson and T. Jordan. Independence free graphs and vertex connectivity augmentation. G. Iyengar and M.T. Cezik. Cutting planes for mixed 0-1 semidefinite programming. M. Kodialam. The throughput of sequential testing. J.B. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1 programs. F. Margot. Pruning by isomorphism in branch-and-cut. A.J. Miller, G.L. Nemhauser and M.W.P. Savelsbergh. Facets and polyhedral characterizations for a multi-item production planning model with setup times. A. Newman and S. Vempala. On the maximum acyclic subgraph problem. M. Perregaard and E. Balas. Generating cuts from multiple-term disjunctions. M. Queyranne and M. Sviridenko. A (2+eps)-approximation algorithm for the generalized preemptive open shop problem with minsum criteria. P. Schuurman and T. Vredeveld. Performance guarantees of local search for multiprocessor scheduling. A. Sebo and E. Tannier. Connected joins in graphs. R. Sitters. On the complexity of preemptive scheduling of unrelated machines. C. Stein and D.P. Wagner. Approximation algorithms for the minimum bends TSP. D.A. van der Laan. Bounds for deterministic periodic routing sequences.