1998

1998: IPCO VI in Houston, USA Program Committee: Imre Barany, Mathematical Institute, Budapest Robert Bixby, Rice University (PC chair) Daniel Bienstock, Columbia University William Cook, Rice University Bert Gerards, CWI, Amsterdam David B. Shmoys, Cornell University David P. Williamson, IBM Watson Research Center List of accepted papers: K. Aardal, A.K. Lenstra, C. Hurkens. An algorithm for solving a Diophantine equation with lower and upper bounds on the variables. H. Abeledo, G.W. Atkinson. Polyhedral combinatorics of Benzenoid problems. A. Barvinok, D.S. Johnson, G.J. Woeginger, R. Woodroofe. Polynomial time algorithms for maximization problems in spaces with polyhedral norms. G. Calinescu, C.G. Fernandes, B. Reed. Multicuts in unweighted graphs with bounded degree and unbounded tree-width. R. Carr, R. Ravi. A new bound for the 2-edge connected subgraph problem. S. Ceria, G. Pataki. Towards a second generation disjunctive program solver. C. Chekuri, M. Bender. Efficient approximation algorithm for minimizing makespan on uniformly related machines. T. Christof, M. Oswald, G. Reinelt. Consecutive ones and a betweenness problem in computational biology. F. Chudak. Improved approximation algorithms for uncapacitated facility location. M. Conforti, A. Kapoor. A Theorem of Truemper. G. Cornuejols, M. Dawande. A class of hard small 0-1 programs. G. Cornuejols, B. Guenin, F. Margot. The packing property. S. Fekete, J. Schepers. New classes of lower bounds for bin packing problems. L. Fleischer. Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time. G. Gasparyan. Bipartite Designs. A. Goldberg, J.D. Oldham, S. Plotkin, C. Stein. An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. B. Guenin. A characterization of weakly bipartite graphs. C. Helmberg, K. Kiwiel, F. Rendl. Incorporating inequality constraints in the spectral bundle method. D. Hochbaum. The pseudoflow algorithm: A new algorithm and a new simplex algorithm for the maximum flow problem. H. Hoogeveen, P. Schuurman, G.J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. V. Kaibel. Polyhedral combinatorics of QAPs with less objects than locations. S.G. Kolliopoulos, C. Stein. Approximation disjoint-path problems using greedy algorithms and packing integer programs. A. Martin, R. Weismantel. The intersection of Knapsack polyhedra and extensions. A. Munier, M. Queyranne, A. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. H. Nagamochi, P. Eades. Edge-splitting and edge-connectivity augmentation in planar graphs. D. Nakamura, A. Tamura. The generalized stable set problem for claw-free bidirected graphs. B. Raghavachari, J. Veerasamy. Approximation algorithms for mixed postman problem. A. Sebo. Characterizing noninteger polyhedra with 0-1 constraints. A. Sebo, J. Cheriyan, Z. Szigeti. An improved approximation algorithm for minimum size 2-edge connected spanning subgraphs. Z. Szigeti. On a min-max theorem of cacti. E. Tardos, K. Wayne. Simple maximum flow algorithms in lossy networks. R. Uma, J. Wein. On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems.