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 is a
vacant PostDoc position, for up to 1 year. The
gross salary is approximately 75.000 CHF per year (taxes around
20%25%). No teaching duties. Generous travel support. 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 POSTDOCSs and VISITING Ph.D. STUDENTs 

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

Mr. Bundit
Laekhanukit, July 2012September 2012. (visitng
student) 

SUPPORTED VISITs 

Andreas Wiese, 2012.  
Danny Hermelin, 2012.  
Kavitha
Telikepalli, 2012. 

Martin Gross, 2012.  
Vincenzo Bonifaci, 2013.  
Yuval Rabani, 2013.  
Zeev Nutov, 2013.  
Matthias Englert, 2013.  
Parinya Chalermsook, 2013.  
SOME PUBLICATIONS 

Utilitarian mechanism design for multiobjective optimization. F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre. To appear in SIAM Journal on Computing.  
New
approaches to multiobjective optimization. F. Grandoni, R.
Ravi, M. Singh, and R. Zenklusen. To appear in Mathematical
Programming. 

A
mazing 2+ε
approximation for unplittable flow on a path A.
Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese.
In SODA, 2014. 

Constant integrality gap LP formulations of unsplittable flow on a path. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. In IPCO, 2013.  
Steiner tree approximation via iterative randomized rounding. J. Byrka, F. Grandoni, T. Rothvoß, L. Sanità. In Journal of the ACM, 2013.  
Tight kernel bounds for problems on graphs with small degeneracy (extended abstract). M. Cygan, F. Grandoni, D. Hermelin. In ESA, 2013.  
How to sell hyperedges: the hypermatching assignment problem. M. Cygan, F. Grandoni, M. Matrolilli. In SODA, 2013.  
On pairwise spanners. M. Cygan, F. Grandoni, and K. Telikepalli. In STACS, 2013.  
Known algorithms for
edge clique cover are probably optimal. M.
Cygan, M.
Pilipczuk, and M.
Pilipczuk. In SODA, 2013. 

Graph products
revisited: Tight approximation hardness of induced matching,
poset dimension, and more. P.
Chalermsook, B. Laekhanukit, D. Nanongkai. In SODA, 2013. 

Set covering with our eyes closed. F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sakowski, M. Singh. In SIAM Journal on Computing, 2013.  
Directed subset feedback vertex set is fixedparameter tractable. R. Chitnis, M. Cygan, M. Hajiaghayi, and D. Marx. In ICALP, 2012.  
Designing FPT
algorithms for cut problems using randomized contractions. R.
Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M.
Pilipczuk. In FOCS, 2012. 

Deterministic
parameterized connected vertex cover. M.
Cygan. In SWAT, 2012. Best
student paper award. 

Algorithmic
applications of BaurStrassen's theorem. M.
Cygan, H. N. Gabow, and P. Sankowski. In FOCS, 2012. 

A pathdecomposition
theorem with applications to pricing and covering on trees. M.
Cygan, F. Grandoni, S. Leonardi, M. Pilipczuk, and P. Sakowski.
In ESA, 2012. 

LP rounding for
kcenters with nonuniform hard capacities. M.
Cygan, M. Hajiaghayi, and S. Khuller.
In FOCS, 2012. 

Steiner forest
orientation problems.
M.
Cygan, G. Kortsarz, and Z. Nutov. In
ESA, 2012. 

Clique cover and graph separation: New incompressibility results. M. Cygan, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and M. Wahlstrom. In ICALP, 2012.  
On group feedback vertex set parameterized by the size of the cutset. M. Cygan, M. Pilipczuk, and M.Pilipczuk. In WG, 2012. Best student paper award.  
Sitting closer to
friends than enemies, revised.
M.
Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. In
MFCS, 2012. 

Improved distance
sensitivity oracles via fast singlesource replacement paths. F.
Grandoni and V. Vassilevska Williams. In FOCS, 2012. 

On minpower Steiner
tree. F.
Grandoni. In ESA, 2012. 

Nonredistributive
second welfare theorems. B.
Laekhanukit, G. Naves, A. Vetta. In WINE, 2012. 

A rounding by sampling approach to the minimum size karc connected subgraph problem. B. Laekhanukit, S. Oveis Gharan, M. Singh. In ICALP, 2012.  
Routing regardless of
network stability. B.
Laekhanukit, A. Vetta, G. Wilfong. In ESA, 2012. 
