victor@WATSON.IBM.COM (Claudio Leonardo Lucchesi) (04/17/91)
\documentstyle[12pt]{article}
\begin{document}
\hyphenation{Cam-pi-nas}
\begin{center}
{\LARGE \bf Campinas Combinatorics Workshop \\
\Large \bf Campinas, SP, Brazil\\
May 20--24, 1991 \\[2cm]
}
\end{center}
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:
\begin{itemize}
\item Routing in Graphs
\item Stable Set Polytopes, Ideal Clutters and their relationship
\end{itemize}
\vspace{.5cm}
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:
\begin{itemize}
\item V. Chv'atal (Rutgers University) - tentative
\item W. Cook (Bellcore)
\item W. Pulleyblank (IBM)
\item B. Reed (University of Waterloo)
\item N. Robertson (Ohio State University) - tentative
\item A. Schrijver (Centrum voor Wiskunde en Informatica, Amsterdam)
\item P. Seymour (Bellcore)
\item B. Shepherd (Centrum voor Wiskunde en Informatica, Amsterdam)
\end{itemize}
\newpage
\noindent Six talks will address ``Routing in Graphs'':
\begin{description}
\item[1 \& 2] Routing with a Fixed Number of Endpoints - P. Seymour
\item[3] Routing in Graphs Embedded on Surfaces - A. Schrijver
\item[4] Linear Time Algorithms for Routing on Surfaces - B. Reed
\item[5] Vehicle Routing Problems - W. Pulleyblank.
\item[6] Recent Computational Experience on the
Travelling Salesman Problem - W. Cook
\end{description}
\vspace*{.5cm}
\noindent ``Stable Set Polytopes and Ideal Clutters'' will be covered in
four talks:
\begin{description}
\item[7] An overview of Perfect Graphs - B. Reed
\item[8] Polynomial-Time Algorithms to Optimize over the
Stable Set Polytope of Perfect Graphs - A. Schrijver
\item[9] On Lehman's Length-Width Inequality - P. Seymour
\item[10] Relationships between Vertex and Clutter Packings - B. Shepherd
\end{description}
\section*{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:
\vspace{.5cm}
\begin{center}
\begin{tabular}{|r@{--}r|*{5}{p{8mm}|}} \cline{3-7}
\multicolumn{2}{c|}
{} &20 &21 &22 &23 &24 \\
\multicolumn{2}{c|}
{} &Mon &Tue &Wed &Thu &Fri \\ \hline
10:00 &11:00 &1 &2 &5 &7 &9 \\ \hline
11:30 &12:30 &3 &4 &6 &8 &10 \\ \hline
2:30 & 3:00 & & &free & & \\ \hline
3:00 & 3:30 & & &free & & \\ \hline
\end{tabular}
\end{center}
\vspace{.5cm}
The sessions will take place at the main auditorium of the Institute of
Mathematics (IMECC), at Unicamp.
\newpage
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?
\section*{Financial Support}
\begin{itemize}
\item CNPq
\item FAPESP
\item IBM Brasil
\item UNICAMP
\end{itemize}
\section*{Organizing Committee}
\begin{tabular}{ll}
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 \\
\end{tabular}
\section*{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).
\section*{For further information contact}
\begin{verse}
Cl'audio L. Lucchesi \\
DCC -- IMECC -- UNICAMP \\
C. Postal 6065 \\
13081 Campinas, SP Brasil \\
+55-192-39-3115 \\
lucchesi@dcc.unicamp.ansp.br \\
\end{verse}
\end{document}