Approximation
Algorithms for Network Problems (APPROXNET) SNSF 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 SNSF) 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 ideal candidate should be bright and creative, and hold (or be close to obtaining) a Master Degree in Computer Science, Mathematics, Physics, or a related area. A solid background in Algorithms, Computational Complexity, Discrete Mathematics, Probability Theory, and/or Graph Theory is helpful. A good knowledge of written and spoken English is also required (while knowledge of Italian is not needed). The positions are currently filled by Waldo Galvez (from November'15) and Afrouz Jabalameli (starting on April'17). In case of any question, feel free to contact Prof. Fabrizio Grandoni at the mentioned email address. 

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 SNSF
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. The position is currently filled by Arindam Khan. 
