Approximation
Algorithms for Network Problems (APPROXNET) SNF Grant 200021_159697/1 

THE PROJECT 

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 highlevel 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 qapproximation 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. Our main research goals can be partitioned into the following two highlevel challenges: 

The duration of this project is 3 years (with possible extensions, subject to approval by SNF) and the project started on November 2015. The total funding is about 680.000 CHF. The project supports two Ph.D. positions and one PostDoc position. 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. 

PHD POSITIONS 

The
project supports two Ph.D. positions for 3 years (with a
possible extension by 1 year, subject to approval by SNF). The
gross salary is according to SNSF guidelines, currently roughly
50.000 CHF per year. There is generous travel support. The positions are currently filled by Waldo Galvez (from November'15) and Afrouz Jabalameli (starting on April'17). 

POSTDOC POSITIONS 

The
project supports one PostDoc position for 3 years. The
appointment will range from 1 to 3 years, depending on the
candidate. The gross salary is according to SNF
guidelines, currently roughly 80.000 CHF per year. There is
generous travel support and there are no 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). He/She should also hold (or be close to obtaining) a Ph.D. in Computer Science. Currently the position is filled by Sumedh Tirodkar. 
