RESEARCH
& PUBLICATIONS
|
I currently have 72 publications (28 journals) with 51
coauthors. According
to Google Scholar, my
papers received over 1400 citations and my h-index is 21. |
RESEARCH
INTERESTS
|
| My
research is focused on the design and analysis of algorithms and
data structures. My main areas of interest are: |
 |
Approximation
algorithms |
[14,15,17,23,27,33,34,39,40,41,45,46,47,48,51,53,54,55,56,57,58,59,60,62,64,67,69,70,71] |
|
Exponential-time
exact algorithms |
[4,5,6,9,10,11,12,16,19,20,21,35,36,37,38,42,49,63,65,68] |
|
Polynomial-time
exact algorithms |
[13,22,25,26,30,43,44,50,61,66,72] |
|
Distributed
algorithms |
[7,8,28,29,31,32,52] |
|
Other
|
[1,2,3,18,24] |
|
PUBLICATIONS
|
| These are the
preprints of some papers of mine. This material is presented to
ensure timely dissemination of scholarly and technical work.
Copyright and all rights therein are retained by authors or by
other copyright holders. All persons copying this information are
expected to adhere to the terms and constraints invoked by each
author's copyright. In most cases, these works may not be reposted
without the explicit permission of the copyright holder. |
To Appear
|
|
72) Data
structures resilient to memory faults: an experimental study
of dictionaries. U.
Ferraro-Petrilllo, F. Grandoni, and G. F. Italiano. To appear in
Journal of Experimental Algorithms. |
|
71)
Set
covering with our eyes closed. F.
Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, M.
Singh. To appear in SIAM Journal
on Computing.
|
2013 |
|
|
|
70)
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),
2013. To appear.
|
|
69) Steiner
tree approximation via iterative randomized rounding.
J. Byrka, F. Grandoni, T. Rothvoß,
and L. Sanità. Journal of the
ACM, 60(1), 2013. |
|
68)
Tight
kernel bounds for problems on graphs with small degeneracy
(Extended Abstract). M.
Cygan, F. Grandoni, D. Hermelin. In
European Symposium on Algorithms (ESA), 2013.
To appear.
|
|
67)
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. |
|
66)
On
pairwise spanners. M.
Cygan, F. Grandoni, and K. Telikepalli.
In
Symposium
on Theoretical Aspects of Computer Science (STACS), 2013. To
appear. |
|
65) Computing
optimal Steiner trees in polynomial space. F.
V. Fomin, F. Grandoni, D. Kratsch, D. Lokshtanov, and S. Saurabh.
Algorithmica, 65(3):
584-604, 2013. |
2012
|
|
|
64)
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.
|
|
63) Sharp
separation and applications to exact and parameterized
algorithms. F.
V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh. Algorithmica,
63(3): 692-706, 2012. |
|
62)
On
min-power Steiner tree. F.
Grandoni. In
European Symposium on Algorithms (ESA), 527-538, 2012.
|
|
61) 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.
|
2011 |
|
60) Budgeted
matching
and budgeted matroid intersection via the gasoline puzzle.
A. Berger, V. Bonifaci, F.
Grandoni, and G. Schäfer. Mathematical
Programming, 128(1-2): 355-372, 2011. |
|
59) Approximation
algorithms for union and intersection covering problems. M.
Cygan, F. Grandoni, S. Leonardi, M. Mucha, M. Pilipczuk, and
P. Sankowski. In Foundations
of Software Technology and Theoretical Computer Science (FSTTCS),
28-40, 2011. |
|
58) Pricing
on paths: a PTAS for the highway problem. F.
Grandoni and T. Rothvoß.
In
ACM-SIAM
Symposium
on Discrete Algorithms (SODA), 675-684, 2011. |
|
57)
Approximation
algorithms for single and multi-commodity connected facility
location. F.
Grandoni and T. Rothvoß.
In Conference
on Integer Programming and Combinatorial Optimization (IPCO),
248-260, 2011. |
|
56) From
uncertainty to non-linearity: Solving virtual private network
via single-sink buy-at-bulk. F.
Grandoni, T. Rothvoß,
and L. Sanità. Mathematics
of Operations Research, 36(2): 185-204, 2011. |
2010 |
|
55) Stable
routing under the spanning tree protocol. F.
Grandoni, G. Nicosia, G. Oriolo, and L. Sanità. Operations
Research Letters, 38(5): 399-404, 2010. |
|
54) Online
network design with outliers. A.
Anagnostopoulos, F. Grandoni, S. Leonardi, and P. Sankowski. In
International Colloquium on Automata, Languages and Programming
(ICALP),
114-126, 2010. |
|
53) An
improved LP-based approximation for Steiner tree.
J. Byrka,
F. Grandoni, T.
Rothvoß, and
L.
Sanità. In
ACM Symposium on Theory of Computing (STOC), 583-592, 2010. Best
Paper Award. |
|
52) Low
degree connectivity of ad-hoc networks via percolation.
E. De Santis, F. Grandoni, and A.
Panconesi. Advances in
Applied Probability, 42(2): 559-576, 2010. |
|
51) Connected
facility location via random facility sampling and core
detouring. F.
Eisenbrand, F. Grandoni, T. Rothvoß,
and G. Schäfer. Journal of
Computer and System Sciences, 76: 709-726, 2010. |
|
50) Data
structures resilient to memory faults: an experimental study
of dictionaries. U. Ferraro-Petrillo,
F. Grandoni, and G. F. Italiano. In
International Symposium on Experimental Algorithms (SEA),
398-410, 2010. |
|
49) Sharp
separation and applications to exact and parameterized
algorithms. F.
V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh. In
Latin American Theoretical Informatics Symposium (LATIN), 72-83,
2010. |
|
48)
Utilitarian
mechanism design for multi-objective optimization.
F.
Grandoni, P. Krysta, S. Leonardi, and C. Ventre. In
ACM-SIAM Symposium on Discrete Algorithms (SODA), 573-584, 2010. |
|
47)
Network
design via core detouring for problems without a core.
F.
Grandoni and T. Rothvoß. In
International Colloquium on Automata, Languages and Programming
(ICALP),
490-502, 2010. |
|
46)
Approximation
schemes for multi-budgeted independence systems. F.
Grandoni
and R. Zenklusen. In
European Symposium on Algorithms (ESA), 536-548, 2010. |
2009 |
|
45) Balanced
cut approximation in random geometric graphs.
J.
Diaz, F. Grandoni, and A. Marchetti-Spaccamela. Theoretical
Computer
Science, 410(27-29): 2725-2731, 2009. |
|
44) Resilient
dictionaries. I.
Finocchi, F. Grandoni, and G. F. Italiano. ACM
Transactions
on Algorithms, 6(1), 2009. |
|
43)
Optimal
resilient sorting and searching in the presence of dynamic
memory faults. I.
Finocchi, F. Grandoni, and G. F. Italiano. Theoretical
Computer
Science, 410(44):
4457--4470, 2009.
Special issue devoted to the best papers of ICALP'06. |
|
42) A
measure & conquer approach for the analysis of exact
algorithms. F. V. Fomin, F.
Grandoni,
and D. Kratsch. Journal
of the ACM 56(5), 2009. |
|
41)
Iterative
rounding for multi-objective optimization problems. F.
Grandoni,
R. Ravi, and M. Singh. In
European Symposium on Algorithms (ESA), 95-106, 2009. |
2008
|
|
40) Budgeted
matching
and budgeted matroid intersection via the gasoline puzzle.
A. Berger, V.
Bonifaci, F. Grandoni, and G. Schäfer. In
Conference on Integer Programming and Combinatorial
Optimization (IPCO), 273-287, 2008.
|
|
|
39)
Approximating
connected facility location problems via random facility
sampling and core detouring. F.
Eisenbrand, F. Grandoni, T. Rothvoß, and
G. Schäfer. In ACM-SIAM Symposium on Discrete Algorithms
(SODA), 1174-1183, 2008.
|
|
38)
Solving
connected
dominating set faster than 2^n. F.
V. Fomin, F. Grandoni, and D. Kratsch.
Algorithmica, 52(2): 153-166, 2008. |
|
37) Faster
Steiner tree computation in polynomial space. F. V.
Fomin, F. Grandoni, and D. Kratsch. In
European Symposium on Algorithms (ESA), 430-441, 2008.
|
|
36) Exact
algorithms for dominating set.
F. V. Fomin, F. Grandoni, and D. Kratsch. Entry
of Encyclopedia of Algorithms, 2008. |
|
35)
Combinatorial
bounds via measure and conquer: bounding minimal dominating
sets and applications. F.
V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov. ACM
Transactions
on Algorithms, 5(1), 2008. |
|
34) Set
covering with our eyes closed. F. Grandoni, A.
Gupta, S. Leonardi, P. Miettinen, P. Sankowski, M. Singh. In
IEEE Symposium on Foundations of Computer Science (FOCS),
347-356, 2008. |
|
33)
A
short proof of the VPN tree routing conjecture on ring
networks. F.
Grandoni, V. Kaibel, G. Oriolo, and M. Skutella.
Operations
Research
Letters, 36(3): 361-365, 2008.
|
|
32)
Distributed
weighted vertex cover via maximal matchings.
F. Grandoni, J. Könemann,
and A. Panconesi. ACM
Transactions
on Algorithms, 5(1), 2008. |
|
31)
A
primal-dual bicriteria distributed algorithm for capacitated
vertex cover.
F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. SIAM
Journal on Computing, 38(3): 825-840, 2008. |
2007
|
|
|
30)
Optimal
resilient
dynamic dictionaries. G. S. Brodal, R.
Fagerberg, I. Finocchi, F. Grandoni, G. F. Italiano, A. G.
Jørgensen, G. Moruz, and T. Mølhave.
In European Symposium on Algorithms (ESA), 347-358, 2007.
|
|
|
29)
Fast
low degree connectivity of ad-hoc networks via percolation.
E. De Santis, F. Grandoni, and A. Panconesi. In European
Symposium on Algorithms (ESA), 206-217, 2007.
|
|
|
28)
Distributed
approximation
algorithms
via LP-duality and randomization.
D. Dubhashi, F. Grandoni, and A. Panconesi.
Chapter 13 of “Handbook of Approximation Algorithms and
Metaheuristics”. Taylor and Francis, 2007.
|
|
|
27)
New
approaches
for virtual private network design. F.
Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. SIAM
Journal on Computing, 37(3):706-721, 2007. |
|
|
26)
Resilient
search trees. I. Finocchi, F. Grandoni,
and G. F. Italiano. In ACM-SIAM Symposium on Discrete
Algorithms (SODA), 547-555, 2007.
|
|
25) Designing
reliable
algorithms in unreliable memories.
I. Finocchi, F. Grandoni, and G. F. Italiano.
Computer
Science Review, 1(2): 77-87, 2007.
|
2006
|
|
|
24)
A
linear time algorithm to list the minimal separators of
chordal graphs. L. S. Chandran and F.
Grandoni. Discrete Mathematics, 306(3):351-358, 2006.
|
|
|
23)
Balanced
cut approximation in random geometric graphs.
J. Diaz, F. Grandoni, and A. Marchetti-Spaccamela. In
International Symposium on Algorithms and Computation (ISAAC),
527-536, 2006.
|
|
|
22)
Optimal
resilient sorting and searching in the presence of memory
faults. I. Finocchi, F. Grandoni, and G.
F. Italiano. In International Colloquium on Automata,
Languages and Programming (ICALP), 286-298, 2006.
|
|
|
21)
Measure
and conquer: a simple O(2^{0.288 n}) independent set
algorithm.
F. Fomin, F. Grandoni, and D. Kratsch. In ACM-SIAM Symposium
on Discrete Algorithms (SODA), 18-25, 2006.
|
|
|
20)
Solving
connected
dominating set faster than 2^n.
F. Fomin, F. Grandoni, and D. Kratsch. In
Foundations
of Software Technology and Theoretical Computer Science
(FSTTCS), 152-163, 2006.
|
|
|
19) A
note on the complexity of minimum dominating set.
F. Grandoni. Journal of Discrete Algorithms, 4(2):209-214,
2006.
|
|
|
18)
Algorithms
and
constraint programming.
F. Grandoni and G. F. Italiano. In
Principles and Practice of Constraint Programming (CP), 2-14,
2006.
|
|
|
17)
Improved
approximation
for single-sink buy-at-bulk.
F. Grandoni and G. F. Italiano. In
International Symposium on Algorithms and Computation (ISAAC),
111-120, 2006.
|
2005
|
|
|
16)
Refined
memorisation
for vertex cover. L. S.
Chandran and F. Grandoni. Information Processing Letters,
93(3):123--131, 2005.
|
|
|
15) An
improved
approximation algorithm for virtual private network design.
F. Eisenbrand and F. Grandoni. In ACM-SIAM Symposium on
Discrete Algorithms (SODA), 928--932, 2005.
|
|
|
14) New
approaches
for virtual private network design. F.
Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. In
International Colloquium on Automata, Languages and
Programming (ICALP), 1151-1162, 2005.
|
|
|
13)
Designing
reliable
algorithms in unreliable memories.
I. Finocchi, F. Grandoni, and G. F. Italiano. In
European Symposium on Algorithms (ESA), 1-8, 2005.
|
|
|
12)
Measure
and conquer: domination - a case study.
F. Fomin, F. Grandoni, and D. Kratsch. In
International Colloquium on Automata, Languages and
Programming (ICALP), 191-203, 2005.
|
|
|
11)
Some
new techniques in design and analysis of exact
(exponential) algorithms.
F.V. Fomin, F. Grandoni, and D. Kratsch. Bulletin of the
European Association for Theoretical Computer Science
87:47--77, 2005.
|
|
|
10)
Bounding
the number of minimal dominating sets: a measure and
conquer approach.
F. Fomin, F. Grandoni, A. Pyatkin, and A. A. Stepanov. In
International Symposium on Algorithms and Computation (ISAAC),
573-582, 2005.
|
|
9) On
the maximum number of minimal dominating sets in graphs.
F. Fomin, F. Grandoni, A. Pyatkin, and A. A. Stepanov. Electronic
Notes in Discrete Mathematics 22: 157-162, 2005. |
|
|
8)
Distributed
weighted
vertex cover via maximal matchings.
F. Grandoni, J. Könemann,
and A. Panconesi. In
International Computing and Combinatorics Conference (COCOON),
839-848, 2005.
|
|
|
7)
Primal-dual
based
distributed algorithms for vertex cover with semi-hard
capacities. F.
Grandoni, J. Könemann,
A. Panconesi, and M. Sozio. In
ACM Symposium on Principles of Distributed Computing (PODC),
118-125, 2005.
|
2004
|
|
6)
Refined
memorisation for vertex cover. L.
S. Chandran and F. Grandoni. In
International Workshop on Parameterized and Exact
Computation (IWPEC), 61-70, 2004. |
|
|
5) On
the complexity of fixed parameter clique and dominating
set. F. Eisenbrand and F. Grandoni. Theoretical
Computer Science, 326(1-3):57-67, 2004.
|
|
|
4) Exact
algorithms
for hard graph problems. F. Grandoni. PhD
thesis, Università di Roma “Tor Vergata”, Roma, Italy, March
2004.
|
|
|
3)
Decremental
clique
problem. F.
Grandoni and G. F. Italiano. In
International Workshop on Graph-Theoretic Concepts in Computer
Science (WG), 142-153, 2004.
|
2003
|
|
|
2)
Detecting
directed
4-cycles still faster. F. Eisenbrand and
F. Grandoni. Information Processing Letters, 87(1):13-15,
2003.
|
|
|
1)
Improved
algorithms
for max-restricted path consistency.
F. Grandoni and G. F. Italiano. In
Principles and Practice of Constraint Programming (CP),
858-862, 2003.
|