New Approaches to Network Design
ERC Starting Grant 279352

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 main goal of this project is to increase our theoretical understanding of networks, with a special focus on faster exact/parametrized algorithms and more accurate polynomial-time approximation algorithms for NP-hard network problems. We will consider classic, challenging open problems in the literature, as well as new, exciting problems arising from the applications. These problems will be addressed with the most advanced algorithmic and analytical tools. A second, ambitious goal of this project is to stimulate the interaction and cross-fertilization between parametrized/exact and approximation algorithms.

The project focuses on (but is not limited to) the following three main research areas:
O Approximation algorithms for network design: the basic goal here is to compute in polynomial time a network which supports a given traffic pattern and whose cost is close to the minimum possible one. Classical network design problems include, e.g., (price-collecting) Steiner tree, TSP, k-MST, and (Connected) Facility Location. Other, more recent, network design problems addressed in the literature are Rent-or-Buy, Buy-at-Bulk, and Virtual Private Network. One can also consider robust, multi-objective, online, game-theoretical or stochastic versions of these problems. We would like to address some relevant open problems, and to study some novel problems arising from the applications.
O Approximation algorithms for pricing problems: here one wants to sell items to a set of customers in order to maximize the total profit. Basic problems include tollbooth, highway, vertex pricing, and their limited-supply, coupon, and envy-free variants. Often the best known approximation algorithms here are (almost) trivial. We would like to increase our theoretical understanding of the approximability of these problems (both in terms of upper and lower bounds). 
O From approximation algorithms to exact ones and back: probably the most common tools to solve exactly NP-hard problems are LP-based heuristics (such as branch-and-bound and cutting-plane methods). These techniques are typically validated experimentally. On the other hand, the goal of parametrized/exact algorithms is to provide non-trivial worst-case upper bounds on the time complexity of those problems. The latter algorithms are most of the times based on rather different (non LP-based) techniques. We would like to explore the design of faster parametrized/exact algorithms via LP-based tools, and vice versa to study some known LP-based heuristics in terms of worst-case running time (at least for restricted classes of problems).   

The project started on January 2012, and will end on December 2016. The total funding is about 1.1 million euros.

There are available short-term PostDoc and visiting Ph.D. student positions (1-2 months). The gross salary is approximately 75.000 CHF and 50.000 CHF per year, respectively (taxes around 15%-25%). No teaching duties.  Here you can find the formal call. Please, e-mail all the required documents also to:

For any question, please contact me at

The project currently supports two Ph.D. students: Salvatore Ingala and Sumedha Gupta. There are no other available Ph.D. positions at the moment.


Mr. Stefano Leucci, June 2015. (visiting student)

Dr. Bundit Laekhanukit, May 2014-August 2014 and January 2015-September 2015. (postdoc)

Mr. Bundit Laekhanukit, July 2012-September 2012. (visiting student)

Dr. Marek Cygan, February 2012-October 2012. (postdoc)


Solomon Lo, 2015.

Marek Adamczyk, 2015.

Rico Zenklusen, 2015.

Stefano Leucci, 2014.

Matthias Mnich, 2014.

Michal Wlodarczyk, 2014.

Tomasz Kociumaka, 2014.

Marek Adamczyk, 2014.

Hyung-Chan An, 2014.
Parinya Chalermsook, 2013.
Matthias Englert, 2013.
Zeev Nutov, 2013.

Yuval Rabani, 2013.

Vincenzo Bonifaci, 2013.

Martin Gross, 2012.

Kavitha Telikepalli, 2012.

Danny Hermelin, 2012.

Andreas Wiese, 2012.


Pricing on paths: a PTAS for the highway problem. F. Grandoni, T. Rothvoß. SIAM Journal on Computing. To appear.

Improved purely additive fault-tolerant spanners. D. Bilò, F. Grandoni, L. Gualà, S. Leucci, and G. Proietti. In European Symposium on Algorithms (ESA), 2015. To appear.

Improved approximation algorithms for Stochastic Matching. M. Adamczyk, F. Grandoni, and J. Mukherjee. In European Symposium on Algorithms (ESA), 2015. To appear.

On conflict-free multi-coloring. A. Bärtschi and F. Grandoni. In Algorithms and Data Structures Symposium (WADS), 2015. To appear.

Subcubic equivalences between graph centrality problems, APSP and Diameter. A. Abboud, F. Grandoni, and V. Vassilevska Williams. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1681-1697, 2015.

On survivable set connectivity. P. Chalermsook, F. Grandoni, and B. Laekhanukit. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 25-36, 2015.

An LP-Rounding 2 sqrt{2}-Approximation for Restricted Maximum Acyclic Subgraph. F. Grandoni, T. Kociumaka, and M. Wlodarczyk. Information Processing Letters, 115: 182-185, 2015.

Utilitarian mechanism design for multi-objective optimization. F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre. SIAM Journal on Computing, 43(4), 1263-1290, 2014.

New approaches to multi-objective optimization. F. Grandoni, R. Ravi, M. Singh, and R. Zenklusen. Mathematical Programming, 146(1-2): 525-554, 2014.

Pre-reduction graph products: Hardness of property learning DFAs and Approximating EDP on DAGs. P. Chalermsook, B. Laekhanukit, and D. NanongkaiIn IEEE Symposium on Foundations of Computer Science (FOCS), 444-453, 2014.

Parameters of two-prover-one-round game and the hardness of connectivity problems. B. Laekhanukit. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1626-1643, 2014.

A Mazing 2+ε Approximation for Unsplittable Flow on a Path. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 26-41, 2014.

Constant integrality gap LP formulations of unsplittable flow on a path. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. In Conference on Integer Programming and Combinatorial Optimization (IPCO), 25-36, 2013.

Steiner tree approximation via iterative randomized rounding. J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. Journal of the ACM, 60(1), 2013.

Tight kernel bounds for problems on graphs with small degeneracy - (Extended Abstract). M. Cygan, F. Grandoni, D. HermelinIn European Symposium on Algorithms (ESA), 361-372, 2013.

How to sell hyperedges: the hypermatching assignment problem. M. Cygan, F. Grandoni, and M. Mastrolilli. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 342-351, 2013.

On pairwise spanners. M. Cygan, F. Grandoni, and K. Telikepalli. In Symposium on Theoretical Aspects of Computer Science (STACS), 209-220, 2013.

Known algorithms for edge clique cover are probably optimal. M. Cygan, M. Pilipczuk, and M. Pilipczuk. In In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1044-1053, 2013.

Graph products revisited: Tight approximation hardness of induced matching, poset dimension, and more. P. Chalermsook, B. Laekhanukit, D. Nanongkai. In In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1557-1576, 2013.

Set covering with our eyes closed. F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, M. Singh. SIAM Journal on Computing, 42(3): 808-830, 2013.

Directed subset feedback vertex set is fixed-parameter tractable. R. Chitnis, M. Cygan, M. Hajiaghayi, and D. Marx. In International Colloquium on Automata, Languages, and Programming (ICALP), 230-241, 2012.

Designing FPT algorithms for cut problems using randomized contractions. R. Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M. Pilipczuk. In IEEE Symposium on Foundations of Computer Science (FOCS), 460-469, 2012.

Deterministic parameterized connected vertex cover. M. Cygan. In Scandinavian Symposium and Workshop on Algorithm Theory (SWAT), 95-106, 2012. Best student paper award.

Algorithmic applications of Baur-Strassen's theorem. M. Cygan, H. N. Gabow, and P. Sankowski. In IEEE Symposium on Foundations of Computer Science (FOCS), 531-540, 2012.

A path-decomposition theorem with applications to pricing and covering on trees. M. Cygan, F. Grandoni, S. Leonardi, M. Pilipczuk, and P. SankowskiIn European Symposium on Algorithms (ESA), 349-360, 2012.

LP rounding for k-centers with non-uniform hard capacities. M. Cygan, M. Hajiaghayi, and S. Khuller. In IEEE Symposium on Foundations of Computer Science (FOCS), 273-282, 2012.

Steiner forest orientation problems. M. Cygan, G. Kortsarz, and Z. Nutov. SIAM Journal on Discrete Mathematics, 27(3): 1503-1513, 2013.

On group feedback vertex set parameterized by the size of the cutset. M. Cygan, M. Pilipczuk, and M.Pilipczuk. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 194-205, 2012. Best student paper award.

Sitting closer to friends than enemies, revised. M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. In International Symposium on Mathematical Foundations of Computer Science (MFCS), 296-307, 2012.

Improved distance sensitivity oracles via fast single-source replacement paths. F. Grandoni and V. Vassilevska WilliamsIn IEEE Symposium on Foundations of Computer Science (FOCS), 748-757, 2012.

On min-power Steiner tree. F. Grandoni. In European Symposium on Algorithms (ESA), 527-538, 2012.

Updated 21/06/2015