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.  
Journal Publications 

Online
network design with outliers. A.
Anagnostopoulos, F. Grandoni, S. Leonardi, and P. Sankowski.
Algorithmica,
76(1), 88109, 2016. 

Pricing on paths: a PTAS for the highway problem. F. Grandoni, T. Rothvoß. SIAM Journal on Computing, 45(2), 216231, 2016.  
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. 

Steiner tree approximation via iterative randomized rounding. J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. Journal of the ACM, 60(1), 2013.  
Data structures resilient to memory faults: an experimental study of dictionaries. U. FerraroPetrilllo, F. Grandoni, and G. F. Italiano. ACM Journal of Experimental Algorithms, 18, 2013.  
Computing optimal Steiner trees in polynomial space. F. V. Fomin, F. Grandoni, D. Kratsch, D. Lokshtanov, and S. Saurabh. Algorithmica, 65(3): 584604, 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.  
Sharp separation and applications to exact and parameterized algorithms. F. V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh. Algorithmica, 63(3): 692706, 2012.  
Budgeted matching and budgeted matroid intersection via the gasoline puzzle. A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer. Mathematical Programming, 128(12): 355372, 2011.  
From uncertainty to nonlinearity: Solving virtual private network via singlesink buyatbulk. F. Grandoni, T. Rothvoß, and L. Sanità. Mathematics of Operations Research, 36(2): 185204, 2011.  
Stable routing under the spanning tree protocol. F. Grandoni, G. Nicosia, G. Oriolo, and L. Sanità. Operations Research Letters, 38(5): 399404, 2010.  
Low degree connectivity of adhoc networks via percolation. E. De Santis, F. Grandoni, and A. Panconesi. Advances in Applied Probability, 42(2): 559576, 2010.  
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: 709726, 2010. 

Balanced cut approximation in random geometric graphs. J. Diaz, F. Grandoni, and A. MarchettiSpaccamela. Theoretical Computer Science, 410(2729): 27252731, 2009.  
Resilient dictionaries. I. Finocchi, F. Grandoni, and G. F. Italiano. ACM Transactions on Algorithms, 6(1), 2009.  
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): 44574470, 2009. Special issue devoted to the best papers of ICALP'06.  
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.  
Solving connected dominating set faster than 2^n. F. V. Fomin, F. Grandoni, and D. Kratsch. Algorithmica, 52(2): 153166, 2008.  
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.  
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): 361365, 2008.  
Distributed weighted vertex cover via maximal matchings. F. Grandoni, J. Könemann, and A. Panconesi. ACM Transactions on Algorithms, 5(1), 2008.  
A primaldual bicriteria distributed algorithm for capacitated vertex cover. F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. SIAM Journal on Computing, 38(3): 825840, 2008.  
New
approaches
for virtual private network design.
F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. SIAM
Journal on Computing, 37(3): 706721, 2007. 

Designing reliable algorithms in unreliable memories. I. Finocchi, F. Grandoni, and G. F. Italiano. Computer Science Review, 1(2): 7787, 2007.  
A linear time algorithm to list the minimal separators of chordal graphs. L. S. Chandran and F. Grandoni. Discrete Mathematics, 306(3): 351358, 2006.  
A note on the complexity of minimum dominating set. F. Grandoni. Journal of Discrete Algorithms, 4(2): 209214, 2006.  
Refined memorization for vertex cover. L. S. Chandran and F. Grandoni. Information Processing Letters, 93(3):123131, 2005.  
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:4777, 2005.  
On the complexity of fixed parameter clique and dominating set. F. Eisenbrand and F. Grandoni. Theoretical Computer Science, 326(13): 5767, 2004.  
Detecting directed 4cycles still faster. F. Eisenbrand and F. Grandoni. Information Processing Letters, 87(1):1315, 2003.  
Conference Publications 

Preserving
distances in very faulty graphs. G.
Bodwin, F. Grandoni, M. Parter, and V. Vassilevska Williams. In
International Colloquium on Automata, Languages and Programming
(ICALP), 2017.
To appear. 

When
the optimum is also blind: a new perspective on universal
optimization. M.
Adamczyk, F. Grandoni, S. Leonardi, and M. Wlodarczyk. In
International Colloquium on Automata, Languages and Programming
(ICALP), 2017.
To appear. 

Surviving
in directed graphs: a quasipolynomialtime polylogarithmic
approximation for twoconnected directed Steiner tree.
F. Grandoni and B. Laekhanukit. In
ACM Symposium on Theory of Computing (STOC), 2017. To appear. 

To
augment or not to augment: solving unsplittable flow on a path
by creating slack. F.
Grandoni, T.
Mömke, A. Wiese, and H. Zhou.
In
ACMSIAM
Symposium
on Discrete Algorithms (SODA), 24112422, 2017. 

Improved
pseudopolynomialtime approximation for strip packing. W.
Galvez, F. Grandoni, S. Ingala, and A. Khan. In Foundations
of Software Technology and Theoretical Computer Science (FSTTCS),
9:19:14, 2016. 

Truly
subcubic algorithms for language edit distance and
RNAfolding via fast boundeddifference minplus product.
K. Bringmann, F. Grandoni, B. Saha, and V. Vassilevska
Williams. In
IEEE Symposium on Foundations of Computer Science (FOCS),
375384, 2016. 

Improved
approximation algorithms for unsplittable flow on a path with
time windows. F.
Grandoni, S. Ingala, and S. Uniyal.
In
Workshop on Approximation and Online Algorithms (WAOA),
1324, 2015. 

Improved
purely additive faulttolerant spanners. D.
Bilò, F.
Grandoni, L. Gualà, S. Leucci, and G. Proietti.
In
European Symposium on Algorithms (ESA),
167178, 2015. 

Improved
approximation algorithms for stochastic matching. M.
Adamczyk, F.
Grandoni, and J. Mukherjee.
In
European Symposium on Algorithms (ESA),
112, 2015. 

On
conflictfree multicoloring. A.
Bärtschi and
F. Grandoni.
In
Algorithms
and Data Structures Symposium (WADS), 103114, 2015. 

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. 

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. 

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. 

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. 

On
minpower Steiner tree. F.
Grandoni. In
European Symposium on Algorithms (ESA), 527538, 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. 

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), 2840, 2011.  
Pricing on paths: a PTAS for the highway problem. F. Grandoni and T. Rothvoß. In ACMSIAM Symposium on Discrete Algorithms (SODA), 675684, 2011.  
Approximation algorithms for single and multicommodity connected facility location. F. Grandoni and T. Rothvoß. In Conference on Integer Programming and Combinatorial Optimization (IPCO), 248260, 2011.  
Online network design with outliers. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and P. Sankowski. In International Colloquium on Automata, Languages and Programming (ICALP), 114126, 2010.  
An improved LPbased approximation for Steiner tree. J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. In ACM Symposium on Theory of Computing (STOC), 583592, 2010. Best Paper Award.  
Data structures resilient to memory faults: an experimental study of dictionaries. U. FerraroPetrillo, F. Grandoni, and G. F. Italiano. In International Symposium on Experimental Algorithms (SEA), 398410, 2010.  
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), 7283, 2010.  
Utilitarian mechanism design for multiobjective optimization. F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre. In ACMSIAM Symposium on Discrete Algorithms (SODA), 573584, 2010.  
Network design via core detouring for problems without a core. F. Grandoni and T. Rothvoß. In International Colloquium on Automata, Languages and Programming (ICALP), 490502, 2010.  
Approximation schemes for multibudgeted independence systems. F. Grandoni and R. Zenklusen. In European Symposium on Algorithms (ESA), 536548, 2010.  
Iterative rounding for multiobjective optimization problems. F. Grandoni, R. Ravi, and M. Singh. In European Symposium on Algorithms (ESA), 95106, 2009.  
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), 273287, 2008. 

Approximating
connected facility location problems via random facility
sampling and core detouring. F.
Eisenbrand, F. Grandoni, T. Rothvoß, and
G. Schäfer. In ACMSIAM Symposium on Discrete Algorithms
(SODA), 11741183, 2008. 

Faster Steiner tree computation in polynomial space. F. V. Fomin, F. Grandoni, and D. Kratsch. In European Symposium on Algorithms (ESA), 430441, 2008.  
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), 347356, 2008.  
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), 347358, 2007. 

Fast low degree connectivity of adhoc networks via percolation. E. De Santis, F. Grandoni, and A. Panconesi. In European Symposium on Algorithms (ESA), 206217, 2007. 

Resilient search trees. I. Finocchi, F. Grandoni, and G. F. Italiano. In ACMSIAM Symposium on Discrete Algorithms (SODA), 547555, 2007. 

Balanced cut approximation in random geometric graphs. J. Diaz, F. Grandoni, and A. MarchettiSpaccamela. In International Symposium on Algorithms and Computation (ISAAC), 527536, 2006. 

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), 286298, 2006. 

Measure and conquer: a simple O(2^{0.288 n}) independent set algorithm. F. Fomin, F. Grandoni, and D. Kratsch. In ACMSIAM Symposium on Discrete Algorithms (SODA), 1825, 2006. 

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), 152163, 2006. 

Algorithms and constraint programming. F. Grandoni and G. F. Italiano. In Principles and Practice of Constraint Programming (CP), 214, 2006. 

Improved approximation for singlesink buyatbulk. F. Grandoni and G. F. Italiano. In International Symposium on Algorithms and Computation (ISAAC), 111120, 2006. 

An improved approximation algorithm for virtual private network design. F. Eisenbrand and F. Grandoni. In ACMSIAM Symposium on Discrete Algorithms (SODA), 928932, 2005. 

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), 11511162, 2005. 

Designing reliable algorithms in unreliable memories. I. Finocchi, F. Grandoni, and G. F. Italiano. In European Symposium on Algorithms (ESA), 18, 2005. 

Measure and conquer: domination  a case study. F. Fomin, F. Grandoni, and D. Kratsch. In International Colloquium on Automata, Languages and Programming (ICALP), 191203, 2005. 

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), 573582, 2005. 

Distributed weighted vertex cover via maximal matchings. F. Grandoni, J. Könemann, and A. Panconesi. In International Computing and Combinatorics Conference (COCOON), 839848, 2005. 

Primaldual based distributed algorithms for vertex cover with semihard capacities. F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. In ACM Symposium on Principles of Distributed Computing (PODC), 118125, 2005.  
Decremental clique problem. F. Grandoni and G. F. Italiano. In International Workshop on GraphTheoretic Concepts in Computer Science (WG), 142153, 2004.  
Improved algorithms for maxrestricted path consistency. F. Grandoni and G. F. Italiano. In International Workshop on GraphTheoretic Concepts in Computer Science (WG), 142153, 2004. 

Other Publications 

E. D. Demaine and F. Grandoni. 8th International Conference on Fun with Algorithms, FUN 2016, June 810, 2016, La Maddalena, Italy. LIPIcs 49, Schloss Dagstuhl  LeibnizZentrum für Informatik 2016, ISBN 9783959770057  
Exact
algorithms for maximum independent set.
F. Grandoni. Entry
of Encyclopedia of Algorithms.
To appear. 

Exact algorithms for dominating set. F. V. Fomin, F. Grandoni, and D. Kratsch. Entry of Encyclopedia of Algorithms, 2008.  
Distributed approximation algorithms via LPduality and randomization. D. Dubhashi, F. Grandoni, and A. Panconesi. Chapter 13 of “Handbook of Approximation Algorithms and Metaheuristics”. Taylor and Francis, 2007.  
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: 157162, 2005.  
Exact algorithms for hard graph problems. F. Grandoni. Ph.D. Thesis, University of Rome "Tor Vergata". Submitted on March 2004. 
