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
|
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:
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
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) |
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.
|
|
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. |
SOME
PUBLICATIONS
|
|
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. Nanongkai. In
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. Hermelin. In
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. Sankowski. In
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
Williams. In
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. |