2002
2002: IPCO IX in Boston, USA Program Committee: Bill Cook, PC-chair, Princeton Satoru Fujishige, Osaka University Alexander Martin, TU Darmstadt Gerhard Reinelt, University of Heidelberg Andreas Schulz, Massachusetts Institute of Technology Andras Sebo, Laboratoire Leibniz Jens Vygen, University of Bonn David P. Williamson, IBM Almaden List of accepted papers: Karen Aardal, Arjen K. Lenstra, Hendrik W. Lenstra, Jr. Hard equality constrained integer knapsacks. Ron Aharoni, Tamas Fleiner. On a lemma of Scarf. Ernst Althaus, Christian Fink. A polyhedral approach to surface reconstruction from contours. Kent Andersen, Gerard Cornuejols, Yanjun Li. Split closure and intersection cuts. Alexander Barvinok, Tamon Stephen. The distribution of values in the quadratic assignment problem. Sylvia Boyd, Genevieve Labonte. Finding the exact integrality gap for small travelling salesman problems. Mao-Cheng Cai, Xiaotie Deng, Haodi Feng, Guojun Li, Guizhen Liu. A PTAS for minimizing total completion time of bounded batch scheduling. Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani. Improved approximation algorithms for resource allocation. Alberto Caprara, Andrea Lodi, Michele Monaci. An approximation scheme for the two-stage, two-dimensional bin packing problem. Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph (Seffi) Naor, Danny Raz. Building edge-failure resilient networks. Sanjeeb Dash. An exponential lower bound on the length of some classes of branch-and-cut proofs. Andreas Eisenblaetter. The semidefinite relaxation of the k-partition polytope is strong. Ismael Regis de Farias, Jr., George L. Nemhauser. A polyhedral study of the cardinality constrained knapsack problem. Lisa Fleischer, Martin Skutella. Simple flows over time. Ari Freund, Joseph (Seffi) Naor. Approximating the advertisement placement problem. Rajiv Gandhi, Samir Khuller, Yoo-Ah Kim, Yung-Chun (Justin) Wan. Algorithms for minimizing response time in broadcast scheduling. Bertrand Guenin. A short proof of Seymour's characterization of the matroids with the max-flow min-cut property. Oktay Gunluk. A new min-cut max-flow ratio for multicommodity flows. Satoru Iwata. A faster scaling algorithm for minimizing submodular functions. Klaus Jansen, Lorant Porkolab. On preemptive resource constrained scheduling: Polynomial-time approximation schemes. Diego Klabjan. A new subadditive approach to integer programming: Theory and algorithms. Adam N. Letchford, Andrea Lodi. Polynomial-time separation of simple comb inequalities. Michael Lewin, Dror Livnat, Uri Zwick. Skewed hyperplane rounding for the MAX 2-SAT and MAX DI-CUT problems. R. Ravi, Amitabh Sinha. Integrated logistics: Approximation algorithms combining facility location and network design. Jean-Philippe P. Richard, Ismael Regis de Farias, George L. Nemhauser. A general theory for the lifting of continuous variables in 0-1 mixed integer programming. Jay Sethuraman, Chung-Piaw Teo, Rakesh V. Vohra. Integer programming and Arrovian social welfare functions. Bruce Shepherd, Adrian Vetta. The demand matching problem. Rene Sitters. The minimum latency problem is NP-hard for weighted trees. Bianca Spille, Robert Weismantel. A combinatorial algorithm for the independent path-matching problem. Maxim Sviridenko. An 1.582-approximation algorithm for the metric uncapacitated facility location problem. Kunal Talwar. Single sink buy-at-bulk LP has constant integrality gap. Akihisa Tamura. Coordinatewise domain scaling algorithm for M-convex function minimization. Klaus M. Wenger. A new approach to cactus construction applied to TSP support graphs.