Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!WATSON.IBM.COM!victor From: victor@WATSON.IBM.COM (Claudio Leonardo Lucchesi) Newsgroups: comp.theory Subject: Campinas Combinatorics Workshop - Announcement in plaintext Message-ID: <9104171625.AA14088@irt.watson.ibm.com> Date: 17 Apr 91 16:25:43 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Theory-A - TheoryNet World-Wide Events , Claudio Leonardo Lucchesi Lines: 157 Campinas Combinatorics Workshop Campinas, SP, Brazil May 20--24, 1991 The 1991 Campinas Combinatorics Workshop will be held on May 20--24, 1991 at the Department of Computer Science, University of Campinas (UNICAMP), Campinas, SP, Brazil. It will focus on two main topics: There will be ten invited talks as well as presentations by some participants of the Workshop. There will also be time left for informal discussions. It is hoped that this relatively unstructured format will foster the free exchange of ideas. The invited speakers are: V. Chv'atal (Rutgers University) - tentative W. Cook (Bellcore) W. Pulleyblank (IBM) B. Reed (University of Waterloo) N. Robertson (Ohio State University) - tentative A. Schrijver (Centrum voor Wiskunde en Informatica, Amsterdam) P. Seymour (Bellcore) B. Shepherd (Centrum voor Wiskunde en Informatica, Amsterdam) Six talks will address ``Routing in Graphs'': 1 & 2 Routing with a Fixed Number of Endpoints - P. Seymour 3 Routing in Graphs Embedded on Surfaces - A. Schrijver 4 Linear Time Algorithms for Routing on Surfaces - B. Reed 5 Vehicle Routing Problems - W. Pulleyblank. 6 Recent Computational Experience on the Travelling Salesman Problem - W. Cook ``Stable Set Polytopes and Ideal Clutters'' will be covered in four talks: 7 An overview of Perfect Graphs - B. Reed 8 Polynomial-Time Algorithms to Optimize over the Stable Set Polytope of Perfect Graphs - A. Schrijver 9 On Lehman's Length-Width Inequality - P. Seymour 10 Relationships between Vertex and Clutter Packings - B. Shepherd Tentative Schedule We have tentatively scheduled these talks for the mornings of May 20--24, with the afternoons left for other presentations and discussions. This is the proposed schedule: 20 21 22 23 24 Mon Tue Wed Thu Fri 10:00 11:00 1 2 5 7 9 11:30 12:30 3 4 6 8 10 2:30 3:00 free 3:00 3:30 free The sessions will take place at the main auditorium of the Institute of Mathematics (IMECC), at Unicamp. What follows is a brief description of the main issues in each of the two topics of the Workshop. {\em Routing} refers to finding paths with given characteristics in graphs. A well known problem in this area is the one of finding internally disjoint paths connecting two subsets $A,B$ of vertices. If no other condition is imposed, then Menger's Theorem gives necessary and sufficient conditions for the existence of such paths. Furthermore a maximum flow algorithm can be used to find the paths in polynomial time, if they exist. However, if $A=(a_1,a_2, \ldots, a_k), B=(b_1, b_2, \ldots ,b_k)$ and we wish to find $k$ disjoint paths whose endpoints are necessarily $(a_1,b_1), (a_2,b_2), \ldots, (a_k,b_k),$ then, in general, determining the existence of such paths is NP-complete. When $k$ is fixed, though, Robertson and Seymour have shown that there is an $O(|VG|^3)$ algorithm to determine whether the $k$ paths exist. If, in addition to fixing $k$, an embedding of the graph in any fixed surface is given, then there is an $O(|VG|)$ algorithm for deciding the existence of the paths. These two polynomial results are the subject of talks 1, 2, 3 and 4. Another popular problem in routing is the {\em Traveling Salesman Problem}: given a graph with weights on the edges, find a closed path that visits every vertex exactly once and has minimum weight among all such paths. Its practical applications and some related computational experience will be the issues of talks 5 and 6. The second topic of the Workshop deals with {\em Polyhedral Combinatorics}. One approach to solving combinatorial optimization problems is to find a linear system $\{Ax \leq b, \;x \geq 0\}$ which defines the set of feasible solutions to the optimization problem. Such a formulation is appealing as it provides a weighted analogue of a min-max theorem. It also yields, through LP duality, an optimality criterion. Often, complete solutions can be obtained by using a system where $A$ and $b$ are either $\{0, 1\}$-valued or $\{0, -1\}$-valued. This is the case for the stable set problem for bipartite graphs and chordal graphs as well as for the max-flow problem in a directed graph. It is then natural to ask for which $\{0, 1\}$ matrices are the polyhedra $\{x : Ax \leq 1, \;x \geq 0\}$ and $\{x : Ax \geq 1, \;x \geq 0\}$ integral? It turns out that such matrices correspond respectively, to the notions of Perfect Graphs and Ideal Clutters. Hence, a $\{0, 1\}$ matrix $A$ is called {\em perfect} (resp. {\em ideal}) if $\{x: Ax \leq 1, \;x \geq 0\}$ (resp. $\{x : Ax \geq 1, \;x \geq 0\}$) is an integral polyhedron. Talks 7, 8, 9 and 10 focus on some of the questions arising in the study of perfect and ideal matrices. For example, is there a good characterization of either of these classes of matrices? Can the associated optimization problems be solved in polynomial time? What similarities exist between perfection and idealism? Can we develop a theory for a common generalization? Financial Support CNPq FAPESP IBM Brasil UNICAMP Organizing Committee Arnaldo Mandel University of S~ao Paulo Cl'audio L. Lucchesi University of Campinas Imre Simon University of S~ao Paulo Jayme L. Szwarcfiter University of Rio de Janeiro Ricardo Dahab University of Campinas Transportation Even though there is an international airport in Campinas, it is more convenient to fly to S~ao Paulo ({\em Guarulhos} International Airport). From S~ao Paulo airport there is a connection by bus to Campinas; this bus departs from {\em Guarulhos} Airport at 11 am, 3 pm, 6:15 pm, 8:30 pm and 10:30 pm, daily, including Saturdays and Sundays. >From S~ao Paulo airport there is also a connection by bus to the Bus Station ({\em Rodovi'aria -- Terminal Tiet^e}). There are buses every 10 minutes, from 5am to midnight, from {\em Terminal Tiet^e} to Campinas (this trip takes 1.5 hours). There are also 3 daily buses directly to Campinas from Rio (6.5 hours). There are domestic flights to S~ao Paulo domestic airport ({\em Congonhas}), mainly from Rio and Belo Horizonte domestic airports ({\em Santos Dumont} and {\em Pampulha}, respectively). For further information contact Cl'audio L. Lucchesi DCC -- IMECC -- UNICAMP C. Postal 6065 13081 Campinas, SP Brasil +55-192-39-3115 lucchesi@dcc.unicamp.ansp.br