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

Accurate Approximation Algorithms: We wish to design more accurate (i.e., with smaller q) polynomial-time approximation algorithms for some NP-hard optimization problems. We will consider both well-studied classical problems and more recent problems arising from the applications. In particular, we wish to investigate some robust and group network design problems, as well as some resource allocation and resource pricing problems. Compromising Time and Accuracy: We wish to develop a better understanding of the possible tradeoffs between running time and approximation factor. On one hand, we will design faster polynomial-time approximation algorithms for some relevant problems. Here we will also consider some polynomial-time-solvable problems that involve very large networks (where a large-degree polynomial running time might be prohibitive in practice). On the other hand, we will design improved approximation algorithms running in slightly super-polynomial time. In particular, we wish to consider quasi-polynomial-time and fixed-parameter-tractable approximation algorithms. 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.

Updated 1st March 2018