Print | Login
graphs/graph_sb_l.gif
français | English
EPFL  >  Faculté SB  >  IMA  >  Recherche Opérati...
splash_rose.jpg

Contact

Professeur Dominique de Werra
MA C1.563 (Bâtiment MA)
Station 8
Téléphone: +41 21 693 2548
Téléfax: +41 21 693 5840
Email: dominique.dewerra@epfl.ch

OR Symposium, June 2008

The Rose co-organizes the OR Symposium of June 30th and July 1st at the EPFL. Plenary lectures will be given by:

 


Armen Asratian
Jacek Blazewicz
Endre Boros
Michele Conforti
Gérard Cornuéjols
Martin Golumbic
Martin Grötschel
Alain Hertz
Jakob Krarup
Vadim Lozin
Nelson Maculan
François Margot

Leslie Trotter

 

More information and registration on http://transp-or2.epfl.ch/ORSymposium/.

Hot news

05.06.2008
New Dr!

On June 5th 2008, Benjamin Leroy-Beaulieu has defended his PhD thesis successfully. We all congratulate him!


01.01.2008
New collaborator!

Today, Dr. Benjamin Lévêque has joined our crew for a six month Post Doc. We are looking forward for this successful collaboration.


Speaker
Dr. Yury Orlovich, United Institute of Informatics Problems (Belarus)
Title
On independent dominating and maximal dissociation sets in graphs
When
Tuesday the 18th of december 2007, 2:15 PM
Where
Room MA 12
Abstract
We consider the complexity and approximability results for the Independent Dominating Set and Independent Neighborhood Set problems within some co-hereditary classes of graphs. We also show that the problem of finding a dissociation set of maximum size in a graph is NP-hard for line graphs, and the problem of finding a maximal dissociation set of minimum size is NP-hard for general graphs. Moreover, some polynomially solvable cases for both problems are derived.


Speaker
Prof. Valery Gordon, United Institute of Informatics Problems (Belarus)
Title
Cyclic properties of triangular grid graphs and locally connected graphs
When
Tuesday, the 11th of December 2007 at 2:15 PM
Where
Room MA 12
Abstract
It is known that all 2-connected, linearly convex triangular grid graphs, with the only one exception, are Hamiltonian (Reay and Zamfirescu, 2000). We show that this result holds for a wider class of connected, locally connected triangular grid graphs and, with more exceptions, even for some general class of graphs. Fully cycle extendibility of connected, locally connected graphs with bounded vertex degree is also considered.


Speaker
Prof. Bezalel Gavish, Southern Methodist University, Dallas, Texas (USA)
Title
Tree Based Combinatorial Optimization Problems in Local Telecommunication Networks
When
Tuesday, 29th of November 2007 at 2:15 PM.
Where
Room MA.B1.504
Summary
Modern Computer Communication Networks are having a profound impact on individuals and society, the demand for higher capacity and faster networking services to the home are increasing significantly over time. This is known as the last mile problem, how to bring broadband communication services to the home at reasonable costs. Several technologies and/or their combinations have been developed to provide such services to the end user: They include Fiberoptics based systems, cable modems and wideband services through the cable TV infrastructure, wireless services through the cellular and wireless based systems and DSL/ADSL and its different variants that is based on extensions of the existing wire based phone system.

The different technologies and the analysis of their advantages and disadvantages will be presented. Most of the technologies rely on the existing local TV cable or phone network to provide services to the home. In order to deploy the technologies efficiently in the local service system efficient algorithms have to be developed to solve existing and new combinatorial optimization problems on tree based networks. We will present several of those problems and highlight results obtained to some of them. Open problems and extensions will be discussed


Speaker
Prof. Wieslaw Kubiak Memorial University, St.John's (Canada)
Title
Webster's sequence for cyclic processes sharing a common resource
When
Tuesday, 12th of June, 2007 at 14h00
Where
Room MA 12
Summary
We consider cyclic processes sharing a common resource. The resource can be used by at most one process at a time. We show that Webster's sequences of apportionment are the most regular words for two cyclic processes, thus they maximize utilization of the resource independently of processing times of the processes. This result is a very rare example where the fair resource allocation ensures its best utilization as well. We also show when Webster's sequences are most regular words for more than two processes by proving a symmetric case of the Fraenkel's conjecture about exact covering of integers by Beatty sequences.


Speaker
Prof. Rainer Burkard
Title
Inverse Location Problems
When
Tuesday, 29th of May, 2007 at 11h00
Where
Room MA 12
Summary
Classical location problems ask for an optimal site from which a finite set of customers can be served as good as possible. The inverse 1-median problem consists in changing the weights of the customers of a 1-median location problem at minimum cost such that a pre-specified point becomes the 1-median. The cost for changing the weights is proportional to the increase or decrease of the corresponding weight. We show that the inverse 1-median problem in trees and in the plane (endowed with the Manhattan metric) can be solved by greedy-like algorithms.

Moreover, we discuss the inverse 1-median problem on a cycle with unit costs for changing the weights. By methods from computational geometry it will be possible to solve this problem in O(n2)-time. Furthermore, a first algorithm for the inverse 1-median problem in the plane endowed with the Euclidean metric and unit costs will be given.

This is a joint work with M. Galavii, E. Gassner, C. Pleschiutschnig and J. Zhang.


SpeakerProf. Gabriele di Stefano
Title Algorithms for railway optimization: the ARRIVAL project
When Thursday, 12.04.2007, 14h
Where
Room MA 31
Summary
Algorithmic methods have reached a state of maturity as a consequence of decades of research where real-world problems were posed to the algorithms community triggering important developments in the field. Despite this success, the current state of algorithmic research still faces severe difficulties, or cannot cope at all, with highly-complex and data-intensive applications as those dealing with optimization issues in large-scale communication and transportation networks.

ARRIVAL (Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large scale systems) is a Specific Targeted Research Project funded by the European Commission within the 6th Framework Programme. ARRIVAL aims to considerably advance the current state of algorithmic research by attacking optimization questions in perhaps the most complex and largest in scale (transportation) setting: that of railway systems. Railway optimization deals with planning and scheduling problems over several time horizons. ARRIVAL faces two important aspects of planning that pose even harder optimization questions: robust planning and online (real-time) planning. These two, tightly coupled, facets constitute a proactive and a reactive approach, respectively, to deal with disruptions to the normal operation.

The seminar gives an overview of some algorithmic problems arising in the areas of timetable information updating, rolling stock scheduling, and delay management.