New
Approaches to Network Design (NEWNET) ERC Starting Grant 279352 

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 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 polynomialtime approximation algorithms for NPhard
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
crossfertilization between parametrized/exact and approximation
algorithms. The project focuses on (but is not limited to) the following three main research areas: 

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

POSTDOCS 

There are
available shortterm PostDoc and visiting Ph.D. student
positions (12 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, email all the required
documents also to: fabrizio@idsia.ch For any question, please contact me at fabrizio@idsia.ch 

PHD 

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

SUPPORTED POSTDOCS AND VISITING PH.D. STUDENTS 

Mr. Stefano Leucci, June 2015. (visiting student)  
Dr. Bundit Laekhanukit, May 2014August 2014 and January 2015September 2015. (postdoc)  
Mr. Bundit
Laekhanukit, July 2012September 2012. (visiting
student) 

Dr. Marek Cygan, February 2012October 2012. (postdoc)  
SUPPORTED VISITS 

Solomon Lo, 2015.  
Marek Adamczyk, 2015.  
Rico Zenklusen, 2015.  
Stefano Leucci, 2014.  
Matthias Mnich, 2014.  
Michal Wlodarczyk, 2014.  
Tomasz Kociumaka, 2014.  
Marek Adamczyk, 2014.  
HyungChan 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.  
SOME PUBLICATIONS 

Pricing on paths: a PTAS for the highway problem. F. Grandoni, T. Rothvoß. SIAM Journal on Computing. To appear.  
Improved purely additive faulttolerant 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 conflictfree multicoloring. 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
ACMSIAM
Symposium
on Discrete Algorithms (SODA), 16811697, 2015. 

On
survivable set connectivity. P.
Chalermsook, F. Grandoni, and B. Laekhanukit.
In
ACMSIAM
Symposium
on Discrete Algorithms (SODA), 2536, 2015. 

An LPRounding 2 sqrt{2}Approximation for Restricted Maximum Acyclic Subgraph. F. Grandoni, T. Kociumaka, and M. Wlodarczyk. Information Processing Letters, 115: 182185, 2015.  
Utilitarian mechanism design for multiobjective optimization. F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre. SIAM Journal on Computing, 43(4), 12631290, 2014.  
New approaches to multiobjective optimization. F. Grandoni, R. Ravi, M. Singh, and R. Zenklusen. Mathematical Programming, 146(12): 525554, 2014.  
Prereduction graph products: Hardness of property learning DFAs and Approximating EDP on DAGs. P. Chalermsook, B. Laekhanukit, and D. Nanongkai. In IEEE Symposium on Foundations of Computer Science (FOCS), 444453, 2014.  
Parameters of twoproveroneround game and the hardness of connectivity problems. B. Laekhanukit. In ACMSIAM Symposium on Discrete Algorithms (SODA), 16261643, 2014.  
A Mazing 2+ε Approximation for Unsplittable Flow on a Path. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. In ACMSIAM Symposium on Discrete Algorithms (SODA), 2641, 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), 2536, 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. Hermelin. In European Symposium on Algorithms (ESA), 361372, 2013.  
How to sell hyperedges: the hypermatching assignment problem. M. Cygan, F. Grandoni, and M. Mastrolilli. In ACMSIAM Symposium on Discrete Algorithms (SODA), 342351, 2013.  
On pairwise spanners. M. Cygan, F. Grandoni, and K. Telikepalli. In Symposium on Theoretical Aspects of Computer Science (STACS), 209220, 2013.  
Known algorithms for
edge clique cover are probably optimal. M.
Cygan, M.
Pilipczuk, and M.
Pilipczuk. In In
ACMSIAM
Symposium
on Discrete Algorithms (SODA),
10441053, 2013. 

Graph products
revisited: Tight approximation hardness of induced matching,
poset dimension, and more. P.
Chalermsook, B. Laekhanukit, D. Nanongkai. In In
ACMSIAM
Symposium
on Discrete Algorithms (SODA),
15571576, 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): 808830, 2013.  
Directed subset feedback vertex set is fixedparameter tractable. R. Chitnis, M. Cygan, M. Hajiaghayi, and D. Marx. In International Colloquium on Automata, Languages, and Programming (ICALP), 230241, 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),
460469, 2012. 

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

Algorithmic
applications of BaurStrassen's theorem. M.
Cygan, H. N. Gabow, and P. Sankowski. In IEEE
Symposium on Foundations of Computer Science (FOCS),
531540, 2012. 

A pathdecomposition theorem with applications to pricing and covering on trees. M. Cygan, F. Grandoni, S. Leonardi, M. Pilipczuk, and P. Sankowski. In European Symposium on Algorithms (ESA), 349360, 2012.  
LP rounding for
kcenters with nonuniform hard capacities. M.
Cygan, M. Hajiaghayi, and S. Khuller.
In IEEE
Symposium on Foundations of Computer Science (FOCS),
273282, 2012. 

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

On group feedback vertex set parameterized by the size of the cutset. M. Cygan, M. Pilipczuk, and M.Pilipczuk. In International Workshop on GraphTheoretic Concepts in Computer Science (WG), 194205, 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),
296307, 2012. 

Improved distance sensitivity oracles via fast singlesource replacement paths. F. Grandoni and V. Vassilevska Williams. In IEEE Symposium on Foundations of Computer Science (FOCS), 748757, 2012.  
On minpower Steiner tree. F. Grandoni. In European Symposium on Algorithms (ESA), 527538, 2012. 
