- One postdoc position for 1 up to 3 years
- One PhD student position for 3+1 years
The position is funded by the Swiss National Science Foundation. This research will be conducted in collaboration and within the Algorithms and Complexity Group at IDSIA.
The positions are available immediately (October 2012).
Project Title: Approximation Algorithms for Machine Scheduling
We want to address and possibly solve some of the open questions in scheduling (see P Schuurman and GJ Woeginger. Polynomial time approximation algorithms for machine scheduling: Ten open problems , Journal of Scheduling 2, 1999, 203--213) which have been open for more than 20 years by now. As Schuurman and Woeginger write "Progress on any of them would be very important" and "it will trigger several breakthroughs in the near future".
Another important part of the project is about techniques. Semidenite Programming (SDP) relaxation in approximating the optimum for combinatorial optimization problems has been one of the most important tools in designing approximation algorithms for combinatorial optimization problems for the last several years. Various hierarchies of these relaxations, such as the ones defined by Sherali and Adams and Lasserre generate increasingly strong semidefinite programming relaxations starting from a basic one. Even though these techniques have recently been successfully applied for several optimization problems, the application of SDP techniques to scheduling problems has been so far rare and very limited. In this project we would like to investigate the positive/negative applications of SDP, and more in general of these hierarchies, where their use yields improved approximation algorithms for scheduling problems.
PhD SALARY: gross salary 45,000 CHF (Swiss Francs) per year (~US$ 48,000 as of September 2012), low taxes (around 20%-25%). 
Postdoc SALARY: gross salary 75,000 CHF per year (~US$ 80,000 as of September 2012). Low taxes (around 20%-25%).
There is travel funding in case of papers accepted at important conferences.
We are looking for an outstanding postdoc and PhD student with excellent mathematical skills and with a background in computer science or mathematics (preferably with a specialization in one of the following topics: combinatorial optimization, discrete mathematics, approximation algorithms, mathematical programming and computational complexity). The right people will have a commitment to research and publication, and possess good communication and presentation skills (in English). The postdoc candidate must have a PhD degree in a relevant field of Computer Science and scientific experience proven by international peer-reviewed publications in approximation algorithms and/or complexity theory. The PhD student candidate must have a MD degree in a relevant field of Computer Science.
The official language at IDSIA is English. The positions are suitable for applicants no older than 35 years.
HOW TO APPLY:
- For the postdoc position, please follow the instructions here. Please, e-mail all the required documents also at: monaldo@idsia.ch
- For the PhD position, applicants should submit as soon as possible: (i) Detailed curriculum vitae, (ii) List of three references and their email addresses, (iii) Concise statement of their research interests (one page max). Send all documents by e-mail to: monaldo@idsia.ch - Monaldo Mastrolilli, IDSIA, Galleria 1, 6928 Manno (Lugano), Switzerland.
