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 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:
|
 |
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. |
|
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).
|
|
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.
|
POSTDOCs
|
The
project supports PostDoc positions for about 6 years altogether.
The positions range from a few months to two years, with
possibility of an extension. 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, e-mail all the required
documents also at:
fabrizio@idsia.ch
For any question, please contact me at: fabrizio@idsia.ch
|
PHD |
The
project supports one Ph.D. position: the position was recently
filled by Salvatore Ingala.
|
SUPPORTED
POSITIONs
|
|
Dr. Marek
Cygan, PostDoc, February 2012-October 2012. |
|
Mr. Bundit
Laekhanukit, Visiting PhD Student, July 2012-September
2012.
|
SUPPORTED VISITs
|
|
Dr. Andreas
Wiese, May 2012. |
|
Dr. Danny
Hermelin, May 2012. |
|
Prof. Kavitha
Telikepalli, May 2012.
|
SELECTED
PUBLICATIONS
|
2013 |
|
Constant integrality gap LP
formulations of unsplittable flow on a path. A.
Anagnostopoulos,
F. Grandoni, S. Leonardi, and A. Wiese. In IPCO 2013. |
|
The hypermatching
assignment problem. M.
Cygan, F. Grandoni, M. Matrolilli. How to Sell Hyperedges. 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.
|
2012 |
|
Directed subset
feedback vertex set is fixed-parameter 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 Baur-Strassen's theorem. M.
Cygan, H. N. Gabow, and P. Sankowski. In FOCS 2012.
|
|
A path-decomposition
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
k-centers with non-uniform 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 single-source replacement paths. F.
Grandoni and V. Vassilevska Williams. In FOCS 2012.
|
|
On min-power Steiner
tree. F.
Grandoni. In ESA 2012.
|
|
Non-redistributive
second welfare theorems. B.
Laekhanukit, G. Naves, A. Vetta. In WINE 2012.
|
|
A rounding by sampling
approach to the minimum size k-arc 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.
|