The candidate will evolve within international environment research taking benefit from different existing and future collaborations. For stochastic aspects of the research, GraphComb has several international bilateral projects with different professors amongst all Professor Gaivoranski from Norwegian University of Science and Technology (NTNU) in Trondheim and Professor Schultz from Duisburg-Essen in Germany.
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 communities. This is especially due to grouping two difficult areas, namely combinatorial and stochastic optimization.
Objectives
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, bioinformatics optimization problems as well as to challenging graph optimization problems, e.g., minimum bandwidth problem, vertex separator problem.
Work program
The objectives are fivefold:
1. Study and design of new algorithms based on semidefinite programming for solving large size minimum bandwidth problems applied to bioinformatics problems.
2. Study and design of new algorithms based on semidefinite programming for solving large size minimum vertex separator.
3. Design new efficient algorithms for solving semidefinite programming problems based on spectral bundle methods.
4. Application of algorithms studied in 3 for solving challenging stochastic combinatorial problems.
5. Apply the previous obtained results to energy management problems and other graph optimization problems.
Extra information
Prerequisite
- Good knowledge of the operations research and probability/statistics fields
- Good programming skills (C, C++, JAVA)
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
Ms Xu Chuan
Utilisateur
abdel.lisser
Créé
Mardi 02 avril 2013 18:24:47 CEST
dernière modif.
Mardi 02 avril 2013 18:24:47 CEST
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
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