graphs/graph_enac_l.gif
English only
INTER  >  TRANSP-OR > 3ième cycle romand de recherche opérationnelle
Logo TRANSP-OR

Zinal

Partners
Content
Links

InformationTop

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.


LecturersTop

Maria Chudnovsky

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, claw-free graphs, even-hole-free graphs and others. We will discuss resent results in the area, as well as some open problems.

Download here a copy of the slides
Maria Chudnovsky

Martin Skutella

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 Max-Planck 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 ground-breaking 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), k-splittable 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.tu-berlin.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:419-433, 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:387-404, 2007.
  • The approximation results with Lisa Fleischer can be found in the article "Quickest Flows Over Time", SIAM Journal on Computing 36:1600-1630, 2007.
  • The work on flows over time with flow-dependent 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:1185­12202, 2005.
    • Ekkehard Koehler, Katharina Langkau, and Martin Skutella "Time-expanded graphs for inflow-dependent transit times", in Proceedings of the 10th Annual European Symposium on Algorithms (ESA), pages 599­611. 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 In-flow-Dependent Transit Times", Algorithmica 47:299­321, 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 399-408, 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.tu-berlin.de/coga/people/skutella/publications.html

Martin Skutella

ScheduleTop

  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

PresentationsTop

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 non-adjacent. A matching M is maximal if no new edge can be added to M without violating the non-adjacency 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 NP-hard 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 NP-hardness of MMM in k-regular 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 NP-complete 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 d-blocker is a subset of edges whose removal decreases the cardinality of a maximum matching by at least d. A d-transversal is a subset of edges which intersect with each maximum matching on at least d edges. We are in particular interested in finding minimum d-blockers and minimum d-transversals. 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 d-blockers and/or minimum d-transversals 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 non-evacuation and non-panic situations. Two main behaviors are identified, unconstrained (free flow conditions) and constrained (interactions with other pedestrians).


RegistrationTop

Sorry, the deadline for registration is over.

Current number of registered participants: 43

  • Altinakar Sivan, ROSE, EPFL
  • Bierlaire Michel, TRANSP-OR, EPFL
  • Buchs Matthias, DIUF, Université de Fribourg
  • Christinat Yann, LCBB - EPFL
  • Chudnovsky Maria, Columbia Unive
  • Cochand Maurice, ETHZ
  • Costantini Liliana, ROSE, EPFL
  • Cruz Javier, TRANSP-OR, EPFL
  • de Werra dominique, ROSE EPFL
  • Eggenberg Niklaus, ENAC INTER TRANSP-OR
  • 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, TRANSP-OR, EPFL
  • Hättenschwiler Pius, University of Fribourg, DIUF
  • Leroy-Beaulieu 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, TRANSP-OR, EPFL
  • Plumettaz Matthieu, ROSE
  • Prodon Alain, ROSO, EPFL
  • Reiner Gerald, University of Neuchâtel
  • Ries Bernard, ROSE, EPFL
  • Robin Thomas, TRANSP-OR, EPFL
  • Rosta Vera, Renyi Institute of Mathematics
  • Salani Matteo, TRANSP-OR, 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, TRANSP-OR, EPFL
  • vanDelft Christian, groupe hec
  • WIdmer Marino, Université de Fribourg - DIUF
  • Zhang Xiuwei, LCBB
  • Zufferey Nicolas, Université de Genève
  • Zwols Yori, Columbia University