Algorithmics-Graphs-Combinatorics
- Domaine
- Algorithmics-Graphs-Combinatorics
- Domain - extra
- Combinatorial Optimization
- Année
- 2011
- Starting
- octobre 2011
- État
- Open
- Sujet
- Stochastic Combinatorial Optimization
- Thesis advisor
- LISSER Abdel
- Co-advisors
- Laboratory
- Collaborations
- Collaboration with Professor Imai from the Technology Institute of Tokyo
- Abstract
- The research topic is Semidefinite Programming and Combinatorial Stochastic Optimization, which is at the crossroads between discrete mathematics, graph theory, optimization and computer science. The project aims at developing new and fast methods for finding exact or approximate solutions to hard combinatorial stochastic optimization problems. Semidefinite programming is a generalization of classic linear programming dealing with optimization problems over positive semidefinite matrices. Working on that and related topics may be part of the PhD research project, as well as algorithmic and computational studies to practical applications amongst all telecommunications network design problems, risk modelling in finance and electricity planning problems.
- Context
- Semidefinite programming is a generalization of classic linear programming dealing with optimization problems over positive semidefinite matrices. Recently, there has been increasing interest in the use of semidefinite programming in solving combinatorial optimization problems. This started with the seminal work of Lovasz (1979) on the so-called theta function. This also led Grötchel, Lovasz and Schrijver (1981) to develop a polynomial time algorithm to solve the maximum stable set problem for perfect graphs. More recently, Goemens and Williamson (1995) improved approximation algorithms for the max cut and related problems using semidefinite programming.
Stochastic combinatorial optimization is a recent topic in optimization, and has met a little interest in the optimization and computer science commnities. This is especially due to grouping two difficult areas, namely combinatorial and stochastic optimization. - Objectives
- The objcetives are four fold:
1. Extend max-k-flow problems to multicommodity problems.
2. Derive semidefinite relaxations in order to build performant polynomial algorthms.
3. Consider the capacities of the edges as random variables, and apply 1. and 2. to the obtained stochastic combinatorial problems.
4. Apply the previous obtained results to survivable network design problems. - Work program
- The main step correpond the 4 objectives described above.
- Extra information
- Prerequisite
- - Research master in computer science or applied mathematics
- Good knowledge of the operations research and probability/statistics fields
- Good programming skills (C, C++) - Détails
Sujet de these 2011 Combinatorics.pdf- Expected funding
- Institutional funding
- Status of funding
- Expected
- Candidates
- Mr. Jean-François Baffier is our favourite candidate for this Ph.D work. Mr. Baffier is preparing his Master degree in Computer Science at the University of Paris Sud. He is preparing his master thesis in Japan under the supervision of Professor Imai in Combinatorial Optimization. He is expected to have an excellent combinatorial optimization education. He is an excellent student and has got very high score in the Master exams.
- Utilisateur
- Créé
- Vendredi 25 mars 2011 14:01:58 CET
- dernière modif.
- Dimanche 26 juin 2011 22:46:46 CEST
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit
Assistante
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr