
The 2008 Spring Seminar of the "3ème cycle romand de Recherche
Opérationnelle" will take place from Sunday January 20 to Thursday January
24 at hôtel de
l'Europe, in Zinal, VS (directions).
Organization: Michel
Bierlaire
Registration deadline: November 30,
2007.
Today is January 30, 2008.
Sorry, the deadline for registration is over.

Maria Chudnovsky received her B.A. and M.Sc. from the
Technion, and a PhD from Princeton University in 2003.
Currently she is an associate professor at Columbia University
and a Clay Mathematics Institute research fellow. Her research
interests are in graph theory and combinatorial optimization.
Recently, she was a part of a team of four researcher that
proved the Strong Perfect Graph Theorem, a forty year old
conjecture, that had been a well known open problem in both
graph theory and combinatorial optimization. 
Excluding induced subgraphs
Our goal is to survey some results concerning the structure
and properties of families of graphs defined by excluding
certain induced subgraphs. Examples of such families are
perfect graphs, clawfree graphs, evenholefree graphs and
others. We will discuss resent results in the area, as well as
some open problems. 
Download
here a copy of the slides  


Martin Skutella received his Ph.D. in Mathematics from TU
Berlin in 1998. He spent one year at the Center for Operations
Research and Econometrics (CORE) in Belgium, one semester at
the Research Institute for Discrete Mathematics in Bonn and
half a year at the Operations Research Center at M.I.T. in
Cambridge. From 2003 to 2004 he was associate professor at
MaxPlanck Institute for Computer Science before he moved to
Dortmund where he held the chair of Discrete Optimization.
Starting October 2007 he is professor at TU Berlin and at DFG
Research Center MATHEON.
His main research interests lie in the area of
Combinatorial Optimization, in particular in Network
Optimization and Scheduling. He is associate editor of the
journals Mathematics for Operations Research, Operation
Research Letters, and Journal of Scheduling. 
Recent directions in network flows and
related problems
Since the groundbreaking work of Ford and Fulkerson in the
1950's the area of network flows has developed into many
interesting directions. Motivated by applications in
transportation, logistics, communication etc. various network
flow models and problems have been studied. We will report on
some recent developments in this area, in particular on
network flows over time (also called "dynamic" network flows),
ksplittable flows and related problems. 
Download
here a copy of the slides 
References:
 The PhD thesis of Bruce Hoppe on "Efficient dynamic
network flow algorithms" gives a very good introduction into
flows over time. A ps file can be found at http://www.math.tuberlin.de/~skutella/hoppe_thesis.ps.gz
 The original paper of Ford and Fulkerson with the title
"Constructing maximal dynamic flows from static flows"
appeared in Operations Research 6:419433, 1958. The result
is also discussed in the book of Ford and Fulkerson on
"Flows in Networks", Princeton University Press, 1962.
 The complexity of multicommodity flows over time is
treated in the paper by Hall, Hippler & Skutella on
"Multicommodity Flows Over Time: Efficient Algorithms and
Complexity" which appeared in Theoretical Computer Science
379:387404, 2007.
 The approximation results with Lisa Fleischer can be
found in the article "Quickest Flows Over Time", SIAM
Journal on Computing 36:16001630, 2007.
 The work on flows over time with flowdependent transit
times can be found in the following three papers:
 Ekkehard Koehler and Martin Skutella "Flows over time
with load dependent transit times", SIAM Journal on
Optimization, 15:118512202, 2005.
 Ekkehard Koehler, Katharina Langkau, and Martin
Skutella "Timeexpanded graphs for inflowdependent
transit times", in Proceedings of the 10th Annual European
Symposium on Algorithms (ESA), pages 599611. Volume
2461 of Lecture Notes in Computer Science. Springer,
Berlin, 2002.
 Alex Hall, Katharina Langkau, and Martin Skutella "An
FPTAS for Quickest Multicommodity Flows with
InflowDependent Transit Times", Algorithmica
47:299321, 2007.
 The work on the evacuation problem with Nadine Baumann
can be found in "Solving Evacuation Problems Efficiently:
Earliest Arrival Flows with Multiple Sources", in
Proceedings of the 47th Annual IEEE Symposium on Foundations
of Computer Science (FOCS '06), pages 399408, 2006.
 Finally, the work on the Virtual Private Network Design
Problem can be found in the paper by Fabrizio Grandoni,
Volker Kaibel, Gianpaolo Oriolo & Martin Skutella, "A
short proof of the VPN tree routing conjecture on ring
networks", Operations Research Letters, to appear.
Most of the papers mentioned above can be found on
Martin Skutella's homepage at http://www.math.tuberlin.de/coga/people/skutella/publications.html
 


Sunday 20 
Monday 21 
Tuesday 22 
Wednesday 23 
Thursday 24 
08h30  09h00 

Skutella 
Chudnovsky 
Skutella 
Chudnovsky 
09h00  09h30 
09h30  10h00 
10h00  10h30 
break 
break 
break 
break 
10h30  11h00 
Chudnovsky 
Skutella 
Chudnovsky 
Skutella 
11h00  11h30 
11h30  12h00 
12h00  17h00 
Sport and discussions 

17h00  17h30 
Skutella 
Thomas Robin 
Tinaz Ekim 
17h30  18h00 
Souleiman Naciri 
Matthias Buchs 
18h00  18h30 
Welcome cocktail 
Benjamin Leveque 
Bernard Ries 
18h30  19h00 


Presentations by PhD students will be organized. Please use the
following form to submit an abstract.
Current number of submitted abstracts: 6
 Buchs Matthias, DIUF, Université de Fribourg
 Model Views: Visual mathematical model inspection
Mathematical models are used in many areas nowadays. Despite the
complexity of real world problems there are currently no general
concepts for visualization of their formalized (modeled) representation.
Decision makers, domain experts and even modelers would profit greatly
from visual aids for model inspection. Our research aims at proposing a
promising modeling language independent concept for mathematical model
inspection. Model views of various complexity and possibly enriched by
semantic information have the potential to improve the understanding of
complex models and therefore leading to better quality of the
latter.
 Ekim  Asici Tinaz, ROSE
 Minimum Maximal Matching – Applications and
Hardness
Given a graph, a matching is a set of edges pairwise nonadjacent. A
matching M is maximal if no new edge can be added to M without violating
the nonadjacency property of its edges. Given a graph, we deal with the
problem of finding a maximal matching of minimum size (MMM for short);
this is NPhard in general. Two applications of MMM (in bipartite
graphs) to evaluate worst case behaviors is outlined; the first one is
related to telephone switching networks, the second one to stable
marriages. We briefly expose the results of Yannakakis and Gavril, and
Horton and Kilakos on the complexity of MMM in restricted classes of
(bipartite) graphs. Then we extend these results by showing the
NPhardness of MMM in kregular bipartite graphs for all k >=3.
 LEVEQUE Benjamin, Rose, EPFL
 Coloring perfect graphs by contraction
Many applied problems can be modelised by the vertex coloring problem
of a graph, which is NPcomplete in general but polynomial on the class
of perfect graphs introduced by Berge. The coloring algorithm of perfect
graphs, due to Grotschel, Lovasz and Schrijver, is not really efficient
in practice and it is still interesting to find a purely combinatorial
algorithm to color perfect graphs in polynomial time. We give several
simple and fast algorithms that enable to color some subclasses of
perfect graphs. These algorithms use in particular the notion of even
pair contraction, introduced by Fonlupt and Uhry, about which several
conjectures are still open. We also use search algorithms like {LexBFS},
due to Rose, Tarjan and Lueker, to prove some structural results on the
considered graphs.
 Naciri Souleiman, LGPP
 Modeling human decision making in supply chain planning by
using interactive simulation
Human beings have a central role in companies and supply chains
behaviour. By making decisions, they can influence the performance of
the whole system either in a good or a bad way. Consequently, the aim of
this research is to model human decision making process within tactical
planning operations. This will be done by using interactive simulation
in which human beings are involved, and must make decisions regarding to
perturbations voluntarity introduced in the simulation tool. By
gathering data about perturbations, context, human characteristics and
decisions, we will be able to model decision making and then to improve
modeling realism.
 Ries Bernard, ROSE, EPFL
 Blockers and transversals
Given an undirected graph G=(V,E), a dblocker is a subset of edges
whose removal decreases the cardinality of a maximum matching by at
least d. A dtransversal is a subset of edges which intersect with each
maximum matching on at least d edges. We are in particular interested in
finding minimum dblockers and minimum dtransversals. First we will
give some basic properties concerning these two notions. Then we present
some complexity results and analyze special classes of graphs for which
minimum dblockers and/or minimum dtransversals can be found in
polynomial time.
 Robin Thomas, Transport and Mobility Laboratory, EPFL
 Specification, estimation and validation of a pedestrian
walking behavior model
Pedestrian behavior modeling is an important topic in different
contexts. For example architects are interested in understanding how
individuals move into buildings to create optimal space designs;
transport engineers face the problem of integration of transportation
facilities, with particular emphasis on safety issues for pedestrians.
We propose and validate a model for pedestrian walking behavior, based
on discrete choice modeling. We are interested in the pedestrian short
range behavior in normal conditions, as a reaction to the surrounding
environment and to the presence of other individuals. With the term
"normal" we refer to nonevacuation and nonpanic situations. Two main
behaviors are identified, unconstrained (free flow conditions) and
constrained (interactions with other pedestrians).
Sorry, the deadline for registration is over.
Current number of registered participants: 43
 Altinakar Sivan, ROSE, EPFL
 Bierlaire Michel, TRANSPOR, EPFL
 Buchs Matthias, DIUF, Université de Fribourg
 Christinat Yann, LCBB  EPFL
 Chudnovsky Maria, Columbia Unive
 Cochand Maurice, ETHZ
 Costantini Liliana, ROSE, EPFL
 Cruz Javier, TRANSPOR, EPFL
 de Werra dominique, ROSE EPFL
 Eggenberg Niklaus, ENAC INTER TRANSPOR
 Ekim  Asici Tinaz, ROSE, EPFL
 Emery Sarah, ROSO, EPFL
 Foniok Jan, IFOR, ETHZ
 Fukuda Komei, EPFL and ETHZ
 Gläßer Dominik, University of Neuchâtel
 Houshang Pour Kamran, TRANSPOR, EPFL
 Hättenschwiler Pius, University of Fribourg, DIUF
 LeroyBeaulieu Benjamin, ROSE EPFL
 LEVEQUE Benjamin, Rose, EPFL
 Liebling Thomas, ROSO EPFL
 Lin Yu, LCBB, EPFL
 Naciri Souleiman, LGPP
 Nieto Yvan, University of Neuchâtel
 Patterson Zachary, TRANSPOR, EPFL
 Plumettaz Matthieu, ROSE
 Prodon Alain, ROSO, EPFL
 Reiner Gerald, University of Neuchâtel
 Ries Bernard, ROSE, EPFL
 Robin Thomas, TRANSPOR, EPFL
 Rosta Vera, Renyi Institute of Mathematics
 Salani Matteo, TRANSPOR, EPFL
 Skutella Martin, TU Berlin
 Svensson Ola, IDSIA
 Track Stephan, Université de Neuchatel
 Trautmann Norbert, Université de Berne
 Tschurtschenthaler Christian, Université de Neuchatel
 Uldry Marc, Université de Fribourg  DIUF
 Vacca Ilaria, TRANSPOR, EPFL
 vanDelft Christian, groupe hec
 WIdmer Marino, Université de Fribourg  DIUF
 Zhang Xiuwei, LCBB
 Zufferey Nicolas, Université de Genève
 Zwols Yori, Columbia University
