DIMACS SPECIAL YEAR - September, 1992 - August, 1993 COMBINATORIAL OPTIMIZATION As part of its program, DIMACS sponsors a variety of activities each year which revolve around a special theme. The special theme for the academic year 1992/93 is combinatorial optimization. This includes a large range of subjects, both theoretical and practical, but some areas of interesting current activity are: - Network flows, disjoint path problems and VLSI design - The travelling salesman problem - Polyhedral approaches to NP-hard problems - Linear and integer programming - Perfect graphs - Matching theory - Related minimax theorems from combinatorics There will probably be four or five workshops, each specializing in a topic such as those listed above, but the exact workshop topics and dates have not yet been decided. ORGANIZING COMMITTEE: L. Lovasz (co-chair), Princeton & Budapest P.D.Seymour (co-chair), Bellcore - V. Chvatal, Rutgers D. Johnson, Bell Labs W. Cook, Bellcore W. Pulleyblank, IBM L. Hall, Princeton A. Schrijver, Amsterdam P. Hammer, Rutgers The theme of the special year is combinatorial optimization, broadly interpreted, and will include research activity, both theoretical and practical, on such topics as the travelling salesman problem (particularly fast heuristics for its solution in practice, but also theoretical approaches); linear programming; integer programming and the variety of techniques for this (approximation methods, heuristic methods, random methods, as well as the deterministic); perfect graphs; network flows, disjoint path problems and VLSI design; matching theory; and related minimax theory from combinatorics. Activities of the special year will be held at all four DIMACS locations, at Rutgers, Princeton, AT&T Bell Labs, and Bellcore. There will be four special year workshops: One on disjoint path problems, November 16-20, 1992, organized by A. Schrijver and P. Seymour; one on probabilistic algorithms for combinatorial optimization, February 22-27, 1993, organized by L. Lovasz; one on computing with NP-hard problems, March 29-April 2, 1993, organized by R. Bixby, W. Cook, and D. Johnson; and one on perfect graphs, May 10-14, 1993, organized by V. Chvatal, L. Lovasz, and B. Reed. There will be a consecutive mini-workshop on perfectly orderable graphs. In addition, there will a number of continuing special year activities, in particular a regular seminar. The special year will host a large number of visitors. Among the visitors expected are C. Colbourn, G. Cornuejols, M. Deza, A. Gerards, M. Loebe, S. Poljak, N. Robertson, A. Schrijver, A. Sebo, D. Shmoys, G. Simonyi, and E. Tardos. Results of the special year will be published in the DIMACS technical report series and in DIMACS volumes, which are published jointly by the Association for Computing Machinery and the American Mathematical Society. Further information about the special year can be obtained from the organizers, in particular Paul Seymour [pds@bellcore.com] and from DIMACS (email address xxxxxxx).