Name and Surname Fabrizio Grandoni

Position Department of Innovative Technologies, Professore

Email fabrizio.grandoni@supsi.ch

Office Polo universitario Lugano, Campus Est, Viganello
Polo universitario Lugano, Campus Est, Via la Santa 1, 6962 Lugano-Viganello

Internal telephone number +41586666590

vCard

Education and training He got a Master Degree in Computer Engineering cum laude at the Universita' di Roma Tor Vergata (Italy) on July 2000. He got a PhD in Computer Science at the same university on May 2004. He spent part of his PhD at the Max Planck Institut fur Informatik (Germany) as a visiting student and as a Marie-Curie Fellow.

Work experience He was a PostDoc in the following Universities and Research Centers: Max Planck Institut fur Informatik (Germany), Universitetet i Bergen (Norway), Sapienza Universita' di Roma (Italy), Technische Universität Berlin (Germany), Ècole Polytechnique Fèdèrale de Lausanne (Switzerland). He was an Assistant Professor at the University of Rome Tor Vergata between 2007 and 2011. He published over 100 papers with more than 80 distinct coauthors on the top journals and conferences of his area. His papers obtained over 3000 citations, and his h-index is 31.

Skills His research is focused on the design and analysis of algorithms and data structures, with a special focus on approximation algorithms. He also works on exact/parameterized algorithms, distributed algorithms, dynamic algorithms, and data structures resilient to memory faults.

Awards - Marie-Curie Doctoral Fellowship, 2002. - Best Paper Award at the ACM Symposium on Theory of Computing, 2010. - ERC Starting Grant, 2011. - EATCS-IPEC Nerode Prize, 2017.

Article in conference proceedings 42 Elements

Anagnostopoulos, A., Grandoni, F., Leonardi, S.& Wiese, A. (2013) Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path., pp.25-36. » more details Cygan, M., Grandoni, F.& Mastrolilli, P. (2013) How to Sell Hyperedges: The Hypermatching Assignment Problem., pp.342-351. » more details Cygan, M., Grandoni, F.& Hermelin, D. (2013) Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract)., pp.361-372. » more details Cygan, M., Grandoni, F.& Kavitha, T. (2013) On Pairwise Spanners., pp.209-220. » more details Grandoni, F., Gupta, A., Leonardi, S., Miettinen, P., Sankowski, P.& Singh, M. (2013) Set Covering with Our Eyes Closed. In Foundations of Computer Science, pp.347-356. » more details Grandoni, F.& Williams, V. (2012) Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths., pp.748-757. » more details Grandoni, F. (2012) On Min-Power Steiner Tree., pp.527-538. » more details Cygan, M., Grandoni, F., Leonardi, S., Pilipczuk, M.& Sankowski, P. (2012) Path-Decomposition Theorem with Applications to Pricing and Covering on Trees, A., pp.349-360. » more details Grandoni, F.& Rothvoß, T. (2011) Pricing on Paths: A PTAS for the Highway Problem., pp.675-684. » more details Grandoni, F.& Rothvoß, T. (2011) Approximation Algorithms for Single and Multi-Commodity Connected Facility Location., pp.248-260. » more details Cygan, M., Grandoni, F., Leonardi, S., Mucha, M., Pilipczuk, M.& Sankowski, P. (2011) Approximation Algorithms for Union and Intersection Covering Problems., pp.28-40. » more details Grandoni, F.& Rothvoß, T. (2010) Network Design via Core Detouring for Problems without a Core., pp.490-502. » more details Grandoni, F., Krysta, P., Leonardi, S.& Ventre, C. (2010) Utilitarian Mechanism Design for Multi-Objective Optimization., pp.573-584. » more details Grandoni, F.& Zenklusen, R. (2010) Approximation Schemes for Multi-Budgeted Independence Systems., pp.536-548. » more details Fomin, F., Lokshtanov, D., Grandoni, F.& Saurabh, S. (2010) Sharp Separation and Applications to Exact and Parameterized Algorithms., pp.72-83. » more details Anagnostopoulos, A., Grandoni, F., Leonardi, S.& Sankowski, P. (2010) Online Network Design with Outliers., pp.114-126. » more details Petrillo, U., Grandoni, F.& Italiano, G. (2010) Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries., pp.398-410. » more details Byrka, J., Grandoni, F., Rothvoß, T.& Sanità, L. (2010) improved LP-based approximation for steiner tree, An., pp.583-592. » more details Grandoni, F., Ravi, R.& Singh, M. (2009) Iterative Rounding for Multi-Objective Optimization Problems., pp.95-106. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2008) Faster Steiner Tree Computation in Polynomial-Space., pp.430-441. » more details Berger, A., Bonifaci, V., Grandoni, F.& Schäfer, G. (2008) Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle., pp.273-287. » more details Grandoni, F., Gupta, A., Leonardi, S., Miettinen, P., Sankowski, P.& Singh, M. (2008) Set Covering with our Eyes Closed., pp.347-356. » more details Eisenbrand, F., Grandoni, F., Rothvoß, T.& Schäfer, G. (2008) Approximating connected facility location problems via random facility sampling and core detouring., pp.1174-1183. » more details De Santis, E., Grandoni, F.& Panconesi, A. (2007) Fast Low Degree Connectivity of Ad-Hoc Networks Via Percolation., pp.206-217. » more details Finocchi, I., Grandoni, F.& Italiano, G. (2007) Resilient search trees., pp.547-553. » more details Brodal, G., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G., Jørgensen, A., Moruz, G.& Mølhave, T. (2007) Optimal Resilient Dynamic Dictionaries., pp.347-358. » more details Grandoni, F.& Italiano, G. (2006) Algorithms and Constraint Programming., pp.2-14. » more details Diaz, J., Grandoni, F.& Marchetti-Spaccamela, A. (2006) Balanced Cut Approximation in Random Geometric Graphs., pp.527-536. » more details Finocchi, I., Grandoni, F.& Italiano, G. (2006) Optimal Resilient Sorting and Searching in the Presence of Memory Faults., pp.286-298. » more details Grandoni, F.& Italiano, G. (2006) Improved Approximation for Single-Sink Buy-at-Bulk., pp.111-120. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2006) Measure and conquer: a simple O(2^{0.288 n}) independent set algorithm., pp.18-25. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2006) Solving Connected Dominating Set Faster Than 2^n., pp.152-163. » more details Eisenbrand, F.& Grandoni, F. (2005) improved approximation algorithm for virtual private network design, An., pp.928-932. » more details Eisenbrand, F., Grandoni, F., Oriolo, G.& Skutella, M. (2005) New Approaches for Virtual Private Network Design., pp.1151-1162. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2005) Measure and Conquer: Domination - A Case Study., pp.191-203. » more details Grandoni, F., Könemann, J., Panconesi, A.& Sozio, M. (2005) Primal-dual based distributed algorithms for vertex cover with semi-hard capacities., pp.118-125. » more details Finocchi, I., Grandoni, F.& Italiano, G. (2005) Designing Reliable Algorithms in Unreliable Memories., pp.1-8. » more details Grandoni, F., Könemann, J.& Panconesi, A. (2005) Distributed Weighted Vertex Cover via Maximal Matchings., pp.839-848. » more details Fomin, F., Grandoni, F., Pyatkin, A.& Stepanov, A. (2005) Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach., pp.573-582. » more details Grandoni, F.& Italiano, G. (2004) Decremental Clique Problem., pp.142-153. » more details Chandran, L.& Grandoni, F. (2004) Refined Memorisation for Vertex Cover., pp.61-70. » more details Grandoni, F.& Italiano, G. (2003) Improved Algorithms for Max-restricted Path Consistency., pp.858-862. » more details

Chapter in book 2 Elements

Kratsch, D., Fomin, F.& Grandoni, F. 2008. Exact Algorithms for Dominating Set. In Encyclopedia of Algorithms. Springer. » more details Dubhashi, D., Grandoni, F.& Panconesi, A. 2007. Distributed approximation algorithms via LP-duality and randomization. In Handbook of Approximation Algorithms and Metaheuristics. Taylor and Francis. » more details

Scientific journal article 27 Elements

Byrka, J., Grandoni, F., Rothvoß, T.& Sanità, L. (2013) Steiner Tree Approximation via Iterative Randomized Rounding. Journal of the ACM, vol. 60 (1) pp.6-6. » more details Petrillo, U., Grandoni, F.& Italiano, G. (2013) Data structures resilient to memory faults: An experimental study of dictionaries. Journal of Experimental Algorithmics, vol. 18. » more details Fomin, F., Grandoni, F., Kratsch, D., Lokshtanov, D.& Saurabh, S. (2013) Computing Optimal Steiner Trees in Polynomial Space. Algorithmica, vol. 65 (3) pp.584-604. » more details Fomin, F., Grandoni, F., Lokshtanov, D.& Saurabh, S. (2012) Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica, vol. 63 (3) pp.692-706. » more details Berger, A., Bonifaci, V., Grandoni, F.& Schäfer, G. (2011) Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming, vol. 128 (1-2) pp.355-372. » more details Grandoni, F., Rothvoß, T.& Sanità, L. (2011) From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk. Journal of Mathematics of Operations Research, vol. 36 (2) pp.185-204. » more details Eisenbrand, F., Grandoni, F., Rothvoß, T.& Schäfer, G. (2010) Connected facility location via random facility sampling and core detouring. Journal of Computer and System Sciences, vol. 76 (8) pp.709-726. » more details Grandoni, F., Nicosia, G., Oriolo, G.& Sanità, L. (2010) Stable routing under the Spanning Tree Protocol. Operations Research Letters, vol. 38 (5) pp.399-404. » more details De Santis, E., Grandoni, F.& Panconesi, A. (2010) Low degree connectivity of ad-hoc networks via percolation. Advances in Applied Probability, vol. 42 (2) pp.559-576. » more details Finocchi, I., Grandoni, F.& Italiano, G. (2009) Resilient dictionaries. ACM Transactions on Algorithms, vol. 6 (1). » more details Diaz, J., Grandoni, F.& Marchetti-Spaccamela, A. (2009) Balanced cut approximation in random geometric graphs. Theoretical Computer Science, vol. 410 (27-29) pp.2725-2731. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2009) measure & conquer approach for the analysis of exact algorithms, A. Journal of the ACM, vol. 56 (5). » more details Finocchi, I., Grandoni, F.& Italiano, G. (2009) Optimal resilient sorting and searching in the presence of memory faults. Theoretical Computer Science, vol. 410 (44) pp.4457-4470. » more details Grandoni, F., Könemann, J., Panconesi, A.& Sozio, M. (2008) Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover, A. SIAM Journal on Computing, vol. 38 (3) pp.825-840. » more details Fomin, F., Grandoni, F., Pyatkin, A.& Stepanov, A. (2008) Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Transactions on Algorithms, vol. 5 (1). » more details Grandoni, F., Kaibel, V., Oriolo, G.& Skutella, M. (2008) short proof of the VPN Tree Routing Conjecture on ring networks, A. Operations Research Letters, vol. 36 (3) pp.361-365. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2008) Solving Connected Dominating Set Faster than 2^n. Algorithmica, vol. 52 (2) pp.153-166. » more details Grandoni, F., Könemann, J.& Panconesi, A. (2008) Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms, vol. 5 (1). » more details Eisenbrand, F., Grandoni, F., Oriolo, G.& Skutella, M. (2007) New Approaches for Virtual Private Network Design. SIAM Journal of Computing, vol. 37 (3) pp.706-721. » more details Finocchi, I., Grandoni, F.& Italiano, G. (2007) Designing reliable algorithms in unreliable memories. Computer Science Review, vol. 1 (2) pp.77-87. » more details Grandoni, F. (2006) note on the complexity of minimum dominating set, A. Journal of Discrete Algorithms, vol. 4 (2) pp.209-214. » more details Chandran, L.& Grandoni, F. (2006) linear time algorithm to list the minimal separators of chordal graphs, A. Discrete Mathematics, vol. 306 (3) pp.351-358. » more details Fomin, F., Grandoni, F., Pyatkin, A.& Stepanov, A. (2005) On maximum number of minimal dominating sets in graphs. Electronic Notes in Discrete Mathematics, vol. 22 pp.157-162. » more details Chandran, L.& Grandoni, F. (2005) Refined memorization for vertex cover. Information Processing Letters, vol. 93 (3) pp.123-131. » more details Fomin, F., Grandoni, F.& Kratsch, D. (2005) Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms. Bulletin of the European Association for Theoretical Computer Science, vol. 87 pp.47-77. » more details Eisenbrand, F.& Grandoni, F. (2004) On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, vol. 326 (1-3) pp.57-67. » more details Eisenbrand, F.& Grandoni, F. (2003) Detecting directed 4-cycles still faster. Information Processing Letters, vol. 87 (1) pp.13-15. » more details

Thesis 1 Element

Grandoni, F. (2004) Exact Algorithms for Hard Graph Problems. University of Rome Tor Vergata. » more details

In charge of the following projects

New Approaches to network Design » more details