Approximation Algorithms for Network Problems II
SNSF Excellence Grant 200020B_182865/1

Networks pervade every aspect of nowadays life. This is one of the reasons why their design, management, and analysis is one of the most active areas of theoretical and empirical research in Computer Science and Operations Research. The high-level goal of this project is to increase our theoretical understanding of networks, with a special focus on the design of fast and accurate approximation algorithms. Informally, a q-approximation algorithm for a given optimization problem is an algorithm that provides a solution whose cost is guaranteed (in the worst case) to be within a factor q > 1 (approximation factor) from the optimal cost.

The duration of this project is 3 years, starting on November 1st 2018
. This is a extension of a previous 3 year project, supported under the new Excellence Grant framework (reserved to the extension of ending top projects). The total funding is about 680.000 CHF. The project supports two Ph.D. positions and two PostDoc positions for up to 2 years each.

Team members will have the opportunity to cooperate with the Algorithms and Complexity group at IDSIA, which currently includes 8 researchers. IDSIA offers an international working environment.

Lugano is a tidy and lively town, with a wonderful view on Ceresio lake and mountains around. Ticino Canton offers many opportunities for hiking, biking, skiing, etc. Restaurants serve very good (Italian style!) food.

The Ph.D. position are filled by Waldo Galvez (since November'15) and Afrouz Jabalameli (since April'17)

The project supports 4 PostDoc years in total, ideally splitted in 2 positions of 1+1 years.  The gross salary is according to SNSF guidelines, currently roughly 80.000 CHF per year. There is generous travel support and there might be light teaching duties.

The ideal candidate should have a strong publication record in the area of algorithms and complexity, possibly in approximation algorithms (e.g., in conferences like STOC, FOCS, SODA, ICALP, ESA). She/He should also hold (or be close to obtaining) a Ph.D. in Computer Science or a related area.

The 2 positions will be soon filled by Dr. Kamiar Khodamoradi (from March 2019) and Dr. Mohit Garg (from June 2019).

Updated 13th February 2019