Prof. Fabrizio Grandoni
Chair of Approximation Algorithms
IDSIA, USI-SUPSI

CONTACTS

Email: fabrizio "at" idsia "dot" ch
Mail address: IDSIA, USI-SUPSI, Polo Universitario Lugano, Campus Est, via la Santa 1, CH-6962 Lugano-Viganello
Office: Room 10, IDSIA, 3rd floor

SHORT BIO

I received a Master degree in Engineering (2000) and a Ph.D. in Computer Science (2004) from the University of Rome Tor Vergata. During my Ph.D. I visited MPII with a Marie-Curie fellowship. After postdoc positions at MPII, University of Rome Sapienza and TU Berlin, in 2007 I joined the University of Rome Tor Vergata as an Assistant Professor. In 2011 I moved to IDSIA, USI-SUPSI, first as a Research Professor and then (from 2019) as a Professor. I made long visits (at least one month) at the University of Bergen (2006), EPFL (2008 and 2009), and at the Simons Institute for the Theory of Computing, Berkeley (2015 and 2016).

I'm married with 2 children. Traveling is my second favorite activity. These are the (54) countries that I visited so far: Australia; Austria; Bahamas; Barbados; Belgium; Bosnia-Herzegovina; Canada; Chile; China; Croatia; Cuba; Czech Republic; Denmark, Egypt; Estonia; Finland; France; Germany; Great Britain; Greece; Hungary; Iceland; India; Ireland; Israel; Italy; Japan; Jordan; Latvia; Liechtenstein; Lithuania; Luxemburg; Malta; Monaco; Mongolia; Morocco; Netherlands; Norway; Peru; Poland; Portugal; Russia; San Marino; Seychelles; Slovenia; Spain; Sweden; Switzerland; Tanzania; Thailand; Tunisia; Turkey; USA; Vatican.

RESEARCH INTERESTS

My research is focused on the design and (mostly theoretical) analysis of algorithms and data structures.  My main area of research is approximation algorithms. I am also interested in efficient algorithms and data structures, dynamic algorithms, online algorithms, parameterized algorithms, and distributed algorithms. I currently have 128 publications (44 journals) with 111 coauthors. Among my 79 peer-reviewed conference papers, 32 are CORE A* (STOC, FOCS, SODA, PODC) and 37 are CORE A (ICALP, ESA, IPCO, SOCG, ITCS, APPROX, STACS, CP, WG, ISAAC). According to Google Scholar my papers received over 4500 citations and my H-index is 39.

PRIZES and AWARDS

  • 2010 Best STOC Paper Award for the paper "An Improved LP-Based Approximation for Steiner Tree" with J. Byrka, T. Rothvoss and L. Sanità.
  • 2017 EATCS-IPEC Nerode prize for the paper "A Measure & Conquer Approach for the Analysis of Exact Algorithms", J. of the ACM 2009, with F. Fomin and D. Kratsch.

GRANTS and FELLOWSHIPS

I'm currently the 

  • PI of the SNSF Grant "Approximation Algorithms for Resource Scheduling", approximately 1400k CHF, 2021-2025.
The high-level goal of this project is to design improved approximation algorithms, with a special focus on 2 families of problems: survivable network design and resource scheduling. This grant is currently supporting 2 Ph.D. students (Antoine Tinguely and Miguel Bosch Calvo) and 2 postdocs (Edin Usic and Krzysztof Sornat). There are no free positions at the moment, but new postdoc positions might be available in the future.

In the past I had the following grants and fellowships:

  • Google Unrestricted Gift for work related to "Scalable, Fair and Accurate Metric Clustering", 30k USD, 2022.
  • PI of the SNSF Excellence Grant "Approximation Algorithms for Network Problems II", approximately 700k CHF, 2018-2021.
  • PI of the SNSF Grant "Approximation Algorithms for Network Problems", approximately 700k CHF, 2015-2018.
  • PI of the ERC Starting Grant "New Approaches to Network Design", approximately 1100k EUR, 2012-2016.
  • Swiss PI of the Indo-Swiss PEP Project "Mathematical Programming in Parameterized Algorithms", approximately 20k CHF, 2012-2014. 
  • Marie-Curie Doctoral Fellowship, MPII, 2002.
I was also a team member of the following Italian projects of National Interest: "Algorithms for Massive Information Structures and Data Streams" (2007-2009); "Algorithmic Challenges for Data-Intensive Processing of Emerging Computing Platforms" (2010-212).

TEACHING

Since 2019 I teach:
  • Advanced Algorithms and Data Structures, Master of Engineering, SUPSI 
  • Approximation Algorithms, Master of Engineering, SUPSI
I previously taught:
  • Algorithms and Complexity, Master of Engineering, SUPSI (2016-2019).
  • Algorithms and Data Structures (under different names), Bachelor of Engineering, University of Rome Tor Vergata (2005-2007, 2009-2012)
  • Introduction to Programming Languages (under different names), Bachelor of Engineering, University of Rome Tor Vergata (2004-2005, 2008-2011)
I also taught the following classes at Ph.D. level:
  • Approximation Algorithms, Bertinoro International Spring School (Italy, 2017)
  • Approximation Algorithms, Gran Sasso Science Institute (Italy, 2016)
  • Advanced Approximation Algorithms, ETHZ (Switzerland, 2014)
  • Advanced Approximation Algorithms, USI (Switzerland, 2013)
  • Iterative Rounding, University of Pisa (Italy, 2013)
  • Measure and Conquer, Spring School on Fixed Parameter and Exact Algorithms (France, 2009)

INSTITUTIONAL WORK

Since April 2021 I'm a proud member of the Swiss National Research Council, in the evaluation panel of Mathematics, Natural and Engineering Sciences.

Since November 2021 I'm a proud full member of the European Association for Theoretical Computer Science (EATCS).

PC WORK

I will be, am or was the chair of the following conferences: FUN16 (co-chair), ESA20 (track A), HALG21.

I will be, am or was in the Steering Committee of the following conference: FUN (2018), HALG (2019-2022), ESA (2020-2024). 

I will be, am or was a PC member of the following 27 conferences: CIAC10, SWAT10, ESA11 (track A), APPROX11, MFCS11, SODA12, SWAT12, ICALP13 (Track A), WAOA13, FUN14, IPEC15, APPROX15, ICALP16 (Track A), SODA16, FSTTCS16, WAOA16, ESA16 (Track B), STOC16, ESA17 (Track A), SPAA17, SODA18, CSR18, APPROX18, FUN18, FOCS19, HALG20, SWAT20, STOC23.

SUPERVISION WORK

I am or was the supervisor of the following Ph.D. students: Salvatore Ingala (2013-2017); Sumedha Uniyal (2013-2017); Waldo Galvez (2015-2019); Afrouz Jabal Ameli (2017-2021); Antoine Tinguely (2021-), Miguel Bosch Calvo (2022-).

I hosted the following postdocs: Marek Cygan (2012); Bundit Laekhanukit (2014-2015); Arindam Khan (2015-2017); Krzysztof Sornat (2018, 2021-); Sumedh Tirodkar (2018-2019); Kamyar Khodamoradi (2019-2020); Mohit Garg (2019-2021); Afrouz Jabal Ameli (2021), Edin Husic (2022-).

I hosted the following visiting Ph.D. students: Bundit Laekhanukit (2012); Joydeep Mukherijee (2014); Stefano Leucci (2015).

REVIEWING WORK

I am or was in the following Editorial Boards: Operations Research Letters (2018-2020); SIAM Journal on Computing (2020-2022, 2023-2025).

I am or was Guest Editor of the following special issues: ACM Transactions on Algorithms (best papers of SODA16); Theoretical Computer Science (best papers of FUN16); Journal of Computer and System Sciences (best papers of ESA20).

I regularly review papers for the most conferences and journals of my area.

I reviewed project proposals for: European Research Council (ERC); Italian Ministry of Research (MIUR); Israel Science Foundation (ISF); Netherlands Organization for Scientific Research (NWO); United States-Israel Binational Science Foundation (BSF); French National Research Agency (ANR).

I was an external committee member for the following Ph.D. defenses: Jesper Nederlof, University of Bergen, 2011; Sandy Heydrich, Saarland University, 2018; Jatin Batra, IIT Dehli, 2019; Sarel Cohen, Tel Aviv University,  2021; Etienne Bamas, EPFL, 2023; Federica Cecchetto ETHZ, 2023.

EVENTS ORGANIZATION

I co-organized the following events:

  • 7th Workshop on Flexible Network Design, Lugano (Switzerland, 2014);
  • HIM Workshop on Approximation and Relaxation, Bonn (Germany, 2021).
  • TheoryFest committee of the ACM Symposium on Theory of Computing (STOC), Rome (Italy, 2022)
  • ACM-SIAM Symposium on Discrete Algorithms (SODA), Local Chair, Florence (Italy, 2023)

INVITED TALKS

I was an invited/plenary speaker at the following conferences and workshops:

  • DIMACS/Princeton Joint Workshop on "Approximation Algorithms: the Last Decade and the Next", Priceton University, USA, 2011
  • ROBOKUM workshop, Germany, 2012
  • ABC workshop on "Combinatorial Optimization Meets Parameterized Complexity", University of Bonn, Germany, 2016
  • European Symposium on Algorithm (ESA), Austria, 2017
  • Italian Conference on Theoretical Computer Science (ICTCS), Italy, 2022
  • DIMAP Theory Day, University of Warwick, Great Britain, 2022
I was invited to participate and give talks at workshops in the following places: Aussois (France, 2005); Bertinoro (Italy, 2005); Bertinoro (Italy, 2006); Kolkata (India, 2006); Dortmund (Germany, 2007); Warwick (Great Britain, 2008); Bertinoro (Italy, 2009); Pisa (Italy, 2009); Chicago (USA, 2009); Dagstuhl (Germany, 2010 twice); Rome (Italy, 2011); Holetown (Barbados, 2011); Warsaw (Poland, 2012); Cargese (France, 2013); Toronto (Canada, 2013); Lausanne (Switzerland, 2013); Bertinoro (Italy, 2014); Lugano (Switzerland, 2014); Warsaw (Poland, 2014); Berkeley (USA, 2015); Pittsburgh (USA, 2015); Bonn (Germany, 2015); Berkeley (USA, 2016); Amsterdam (Netherlands, 2016);  Banff (Canada, 2017); Shonan (Japan, 2017); Berkeley (USA, 2017);  Bonn (Germany, 2018); Bordeaux (France, 2018); Maryland (USA, 2018); Bertinoro (Italy, 2019); Cargese (France, 2019); Venezia (Italy, 2019); Bonn (Germany, 2021); Dagstuhl (Germany, 2022); Dagstuhl (Germany, 2023). 

MISCELLANEA

These are a few articles (in Italian) that mention my work: Ticino Scienza 28-05-2021, Corriere della Sera 15-09-2011, Sole 24 Ore 03-08-2011, Sole 24 Ore 04-08-2010, Corriere della Sera 29-03-2010.

I obtained the Italian Scientific Habilitation to Full Professorship in Computer Science for the Science Track (INF/01) in 2013, and for the Engineering Track (ING-INF/05) in 2015.

In 2010 I received a Letter of Commendation (in Italian) of the Rector of the University of Rome Tor Vergata for my scientific merits. 

I am a founding member of the Interest Group on Algorithmic Foundations of Information Technology (IGAFIT, 2014-).

I initiated and currently co-organize the IDSIA lunch seminars PIDSIA (Pizza at IDSIA).

Since 2019 I belong to the network of "advocates" who help to implement the recommendations of the ad hoc committee to combat harassment and discrimination at TCS conferences.

I appear in the 9th edition of the Research.com ranking of the world best scientists in Computer Science (position 9890). 

PUBLICATIONS

These are the preprints of my published papers. 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 some cases, these works may not be reposted without the explicit permission of the copyright holder.

Journals

Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. J. Byrka, F. Grandoni, A. Jabal Ameli. SIAM Journal on Computing. To appear.

A tight (3/2+ε) approximation for skewed strip packing. W. Galvez, F. Grandoni, A. Jabal Ameli, K. Jansen, A. Khan, M. Rau. Algorithmica. To appear.

Subcubic equivalences between graph centrality problems, APSP and Diameter. A. Abboud, F. Grandoni, and V. Vassilevska Williams. ACM Transactions on Algorithms,19(1): 3:1-3:30, 2023.

A refined approximation for Euclidean k-means. F. Grandoni, R. Ostrovsky, Y. Rabani, L. J. Schulman, and R. Venkat. Information Processing Letters, 176: 106251, 2022.

Fully dynamic (Δ+1)-coloring in O(1) update time. S. Bhattacharya, F. Grandoni, J. Kulkarni, Q. C. Liu, and S. Solomon. ACM Transactions on Algorithms, 18(2): 10:1-10:25, 2022.

Approximating geometric knapsack via L-packings. W. Galvez, F. Grandoni, S. Heydrich, S. Ingala, and A. Khan, A. Wiese. ACM Transactions on Algorithms, 17(4): 33:1-33:67, 2021.

On the cycle augmentation problem: hardness and approximation algorithms. W. Galvez, F. Grandoni, A. Jabal Ameli, and K. Sornat. Theory of Computing Systems 65(6): 985-1008, 2021.

Faster replacement paths and distance sensitivity oracles.  F. Grandoni and V. Vassilevska Williams. ACM Transactions on Algorithms, 16(1): 15:1-15:25, 2020.

The matching augmentation problem: a 7/4-approximation algorithm. J. Cheriyan, J. Dippel, F. Grandoni, A. Khan, and V.V. Narayan. Mathematical Programming, 182(1): 315-354, 2020.

Truly sub-cubic algorithms for language edit distance and RNA-folding via fast bounded-difference min-plus product. K. Bringmann, F. Grandoni, B. Saha, and V. Vassilevska Williams. SIAM Journal on Computing, 48(2): 481-512, 2019. Special issue devoted to the best papers of FOCS'16.

A mazing 2+ε approximation for unsplittable flow on a path. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. ACM Transactions on Algorithms, 14(4): 55:1-55:23, 2018.

Tight kernel bounds for problems on graphs with small degeneracy. M. Cygan, F. Grandoni, D. HermelinA. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. ACM Transactions on Algorithms, 13(3): 43:1-43:22, 2017.

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

Pricing on paths: a PTAS for the highway problem. F. Grandoni and T. Rothvoß. SIAM Journal on Computing, 45(2), 216-231, 2016.

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.

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. Ferraro-Petrilllo, 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): 584-604, 2013.

Set covering with our eyes closed. F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, and M. Singh. SIAM Journal on Computing, 42(3): 808-830, 2013.

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.

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.

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.

Stable routing under the spanning tree protocol. F. Grandoni, G. Nicosia, G. Oriolo, and L. Sanità. Operations Research Letters, 38(5): 399-404, 2010.

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.

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.

Balanced cut approximation in random geometric graphs. J. Diaz, F. Grandoni, and A. Marchetti-Spaccamela. Theoretical Computer Science, 410(27-29): 2725-2731, 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): 4457--4470, 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. EATCS NERODE PRIZE.

Solving connected dominating set faster than 2^n. F. V. Fomin, F. Grandoni, and D. Kratsch. Algorithmica, 52(2): 153-166, 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): 361-365, 2008.

Distributed weighted vertex cover via maximal matchings. F. Grandoni, J. Könemann, and A. Panconesi. ACM Transactions on Algorithms, 5(1), 2008.

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.

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.

Designing reliable algorithms in unreliable memories. I. Finocchi, F. Grandoni, and G. F. Italiano. Computer Science Review, 1(2): 77-87, 2007.

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.

A note on the complexity of minimum dominating set. F. Grandoni. Journal of Discrete Algorithms, 4(2): 209-214, 2006.

Refined memorization for vertex cover. L. S. Chandran and F. Grandoni. Information Processing Letters, 93(3):123--131, 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:47--77, 2005.

On the complexity of fixed parameter clique and dominating set. F. Eisenbrand and F. Grandoni. Theoretical Computer Science, 326(1-3): 57-67, 2004.

Detecting directed 4-cycles still faster. F. Eisenbrand and F. Grandoni. Information Processing Letters, 87(1):13-15, 2003.

Conferences

A 4/3 approximation for 2-vertex-connectivity. M. Bosch-Calvo, F. Grandoni, and A. Jabal Ameli. International Colloquium on Automata, Languages and Programming (ICALP), 2023. To appear. BEST PAPER AWARD.

Unsplittable Euclidean capacitated vehicle routing: a (2+ε)-approximation algorithm. F. Grandoni, C. Mathieu, and H. Zhou. Innovations in Theoretical Computer Science (ITCS), 63:1-63:12, 2023.

Breaching the 2 LMP approximation barrier for facility location and applications to k-median. V. Cohen-Addad, F. Grandoni, E. Lee, and C. Schwiegelshohn. ACM-SIAM Symposium on Discrete Algorithms (SODA), 940-986, 2023.

Improved approximation for two-edge-connectivity. M. Garg, F. Grandoni, and A. Jabal Ameli. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2368-2410, 2023.

Breaching the 2-approximation barrier for the forest augmentation problem. F. Grandoni, A. Jabal Ameli, and V. Traub. ACM Symposium on Theory of Computing (STOC), 1598-1611, 2022.

A PTAS for unsplittable flow on a path. F. Grandoni, T. Mömke, and A. Wiese. ACM Symposium on Theory of Computing (STOC), 289-302, 2022.

Unsplittable flow on a path: the game!. F. Grandoni, T. Mömke, and A. Wiese. ACM-SIAM Symposium on Discrete Algorithms (SODA),906-926, 2022.

Maintaining and EDCS in general graphs: simpler, density-sensitive and with worst-case time bounds. F. Grandoni, C. Schwiegelshohn, S. Solomon, and A. Uzrad. SIAM Symposium on Simplicity in Algorithms (SOSA), 12-23, 2022.

Faster (1+ε) approximation for unsplittable flow on a path via resource augmentation and back. F. Grandoni, T. Mömke, and A. Wiese. European Symposium on Algorithms (ESA), 49:1-49:15, 2021.

Approximation algorithms for demand strip packing. W. Galvez, F. Grandoni, A. Jabal Ameli, K. Khodamoradi. APPROX/RANDOM, 20:1-20:24, 2021.

Improved approximation algorithms for 2-dimensional knapsack: packing into multiple L-shapes, spirals, and more. W. Galvez, F. Grandoni, A. Khan, D. Ramirez-Romero, A. Wiese. International Symposium on Computational Geometry (SoCG), 39:1-39:17, 2021.

Online Edge Coloring Algorithms via the Nibble Method. S. Bhattacharya, F. Grandoni, D. Wajc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2830-2842, 2021.

All-pairs LCA in DAGs: breaking through the  O(n^2.5) barrier. F. Grandoni, G. Italiano, A. Lukasiewicz, N. Parotsidis, P. Uznanski. ACM-SIAM Symposium on Discrete Algorithms (SODA), 273-289, 2021.

A tight (3/2+ε) approximation for skewed strip packing. W. Galvez, F. Grandoni, A. Jabal Ameli, K. Jansen, A. Khan, M. Rau. APPROX/RANDOM, 44:1-44:18, 2020.

Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. J. Byrka, F. Grandoni, A. Jabal Ameli. ACM Symposium on Theory of Computing (STOC), 815-825, 2020.

On the cycle augmentation problem: hardness and approximation algorithms. W. Galvez, F. Grandoni, A. Jabal Ameli, and K. Sornat. Workshop on Approximation and Online Algorithms (WAOA), 138-153,  2019.

Parameterized approximation schemes for independent set of rectangles and geometric knapsack. F. Grandoni, S. Kratsch, and A. Wiese. European Symposium on Algorithms (ESA), 53:1-53:16, 2019.

Packing cars into narrow roads: PTASs for limited supply highway. F. Grandoni and A. Wiese. European Symposium on Algorithms (ESA), 54:1-54:14, 2019.

Dynamic set cover: improved algorithms and lower bounds. A. Abboud, R. Addanki, F. Grandoni, D. Panigrahi, B. Saha. ACM Symposium on Theory of Computing (STOC), 114-125, 2019.

Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. L. Becchetti, M. Bury, V. Cohen-Addad, F. Grandoni, C. Schwiegelshohn. ACM Symposium on Theory of Computing (STOC), 1039-1050, 2019.

O(log^2 k/loglog k) approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. F. Grandoni, B. Laekhanukit, S. Li. ACM Symposium on Theory of Computing (STOC), 253-264, 2019.

(1+ε)-Approximate incremental matching in constant deterministic amortized time. F. Grandoni, S. Leonardi, P. Sankowski, C. Schwiegelshohn, S. Solomon. ACM-SIAM Symposium on Discrete Algorithms (SODA), 1886-1898, 2019.

Improved approximation for tree augmentation: saving by rewiring. F. Grandoni, C. Kalaitzis, and R. Zenklusen. ACM Symposium on Theory of Computing (STOC), 632-645, 2018.

A (5/3+ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. F. Grandoni, T. Mömke, A. Wiese, and H. Zhou. ACM Symposium on Theory of Computing (STOC), 607-619, 2018.

Approximating geometric knapsack via L-packings. W. Galvez, F. Grandoni, S. Heydrich, S. Ingala, and A. Khan, A. Wiese. IEEE Symposium on Foundations of Computer Science (FOCS), 260-271, 2017.

Preserving distances in very faulty graphs. G. Bodwin, F. Grandoni, M. Parter, and V. Vassilevska Williams. International Colloquium on Automata, Languages and Programming (ICALP), 73:1-73:14, 2017.

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

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree. F. Grandoni and B. Laekhanukit. ACM Symposium on Theory of Computing (STOC), 420-428, 2017.

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. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2411-2422, 2017.

Improved pseudo-polynomial-time approximation for strip packing. W. Galvez, F. Grandoni, S. Ingala, and A. Khan. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 9:1-9:14, 2016.

Truly sub-cubic algorithms for language edit distance and RNA-folding via fast bounded-difference min-plus product. K. Bringmann, F. Grandoni, B. Saha, and V. Vassilevska Williams. IEEE Symposium on Foundations of Computer Science (FOCS), 375-384, 2016.

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

Improved purely additive fault-tolerant spanners. D. Bilò, F. Grandoni, L. Gualà, S. Leucci, and G. Proietti. European Symposium on Algorithms (ESA), 167-178, 2015.

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

On conflict-free multi-coloring. A. Bärtschi and F. Grandoni. Algorithms and Data Structures Symposium (WADS), 103-114, 2015.

Subcubic equivalences between graph centrality problems, APSP and Diameter. A. Abboud, F. Grandoni, and V. Vassilevska Williams. ACM-SIAM Symposium on Discrete Algorithms (SODA), 1681-1697, 2015.

On survivable set connectivity. P. Chalermsook, F. Grandoni, and B. Laekhanukit. ACM-SIAM Symposium on Discrete Algorithms (SODA), 25-36, 2015.

A Mazing 2+ε Approximation for Unsplittable Flow on a Path. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese. 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.  Conference on Integer Programming and Combinatorial Optimization (IPCO), 25-36, 2013.

Tight kernel bounds for problems on graphs with small degeneracy - (Extended Abstract). M. Cygan, F. Grandoni, D. Hermelin. European Symposium on Algorithms (ESA), 361-372, 2013.

How to sell hyperedges: the hypermatching assignment problem. M. Cygan, F. Grandoni, and M. Mastrolilli. ACM-SIAM Symposium on Discrete Algorithms (SODA), 342-351, 2013.

On pairwise spanners. M. Cygan, F. Grandoni, and K. Telikepalli. Symposium on Theoretical Aspects of Computer Science (STACS), 209-220, 2013.

A path-decomposition theorem with applications to pricing and covering on trees. M. Cygan, F. Grandoni, S. Leonardi, M. Pilipczuk, and P. Sankowski. European Symposium on Algorithms (ESA), 349-360, 2012.

On min-power Steiner tree. F. Grandoni. European Symposium on Algorithms (ESA), 527-538, 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.

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.

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.

Approximation algorithms for single and multi-commodity connected facility location. F. Grandoni and T. Rothvoß. Conference on Integer Programming and Combinatorial Optimization (IPCO), 248-260, 2011.

Online network design with outliers. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and P. Sankowski. International Colloquium on Automata, Languages and Programming (ICALP), 114-126, 2010.

An improved LP-based approximation for Steiner tree. J. Byrka,  F. Grandoni, T. Rothvoß, and L. Sanità. ACM Symposium on Theory of Computing (STOC), 583-592, 2010. BEST PAPER AWARD.

Data structures resilient to memory faults: an experimental study of dictionaries. U. Ferraro-Petrillo,  F. Grandoni, and G. F. Italiano. International Symposium on Experimental Algorithms (SEA), 398-410, 2010.

Sharp separation and applications to exact and parameterized algorithms. F. V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh. Latin American Theoretical Informatics Symposium (LATIN), 72-83, 2010.

Utilitarian mechanism design for multi-objective optimization. F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre. ACM-SIAM Symposium on Discrete Algorithms (SODA), 573-584, 2010.

Network design via core detouring for problems without a core. F. Grandoni and T. Rothvoß. International Colloquium on Automata, Languages and Programming (ICALP), 490-502, 2010.

Approximation schemes for multi-budgeted independence systems. F. Grandoni and R. Zenklusen. European Symposium on Algorithms (ESA), 536-548, 2010.

Iterative rounding for multi-objective optimization problems. F. Grandoni, R. Ravi, and M. Singh. European Symposium on Algorithms (ESA), 95-106, 2009.

Budgeted matching and budgeted matroid intersection via the gasoline puzzle. A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer. Conference on Integer Programming and Combinatorial Optimization (IPCO), 273-287, 2008.

Approximating connected facility location problems via random facility sampling and core detouring. F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. ACM-SIAM Symposium on Discrete Algorithms (SODA), 1174-1183, 2008.

Faster Steiner tree computation in polynomial space. F. V. Fomin, F. Grandoni, and D. Kratsch. European Symposium on Algorithms (ESA), 430-441, 2008.

Set covering with our eyes closed. F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, M. Singh. IEEE Symposium on Foundations of Computer Science (FOCS), 347-356, 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. European Symposium on Algorithms (ESA), 347-358, 2007.

Fast low degree connectivity of ad-hoc networks via percolation. E. De Santis, F. Grandoni, and A. Panconesi. European Symposium on Algorithms (ESA), 206-217, 2007.

Resilient search trees. I. Finocchi, F. Grandoni, and G. F. Italiano. ACM-SIAM Symposium on Discrete Algorithms (SODA), 547-555, 2007.

Balanced cut approximation in random geometric graphs. J. Diaz, F. Grandoni, and A. Marchetti-Spaccamela. International Symposium on Algorithms and Computation (ISAAC), 527-536, 2006.

Optimal resilient sorting and searching in the presence of memory faults. I. Finocchi, F. Grandoni, and G. F. Italiano. International Colloquium on Automata, Languages and Programming (ICALP), 286-298, 2006.

Measure and conquer: a simple O(2^{0.288 n}) independent set algorithm. F. Fomin, F. Grandoni, and D. Kratsch. ACM-SIAM Symposium on Discrete Algorithms (SODA), 18-25, 2006.

Solving connected dominating set faster than 2^n. F. Fomin, F. Grandoni, and D. Kratsch. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 152-163, 2006.

Algorithms and constraint programming. F. Grandoni and G. F. Italiano. Principles and Practice of Constraint Programming (CP), 2-14, 2006.

Improved approximation for single-sink buy-at-bulk. F. Grandoni and G. F. Italiano. International Symposium on Algorithms and Computation (ISAAC), 111-120, 2006.

An improved approximation algorithm for virtual private network design. F. Eisenbrand and F. Grandoni. ACM-SIAM Symposium on Discrete Algorithms (SODA), 928--932, 2005.

New approaches for virtual private network design. F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. International Colloquium on Automata, Languages and Programming (ICALP), 1151-1162, 2005.

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

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

Bounding the number of minimal dominating sets: a measure and conquer approach. F. Fomin, F. Grandoni, A. Pyatkin, and A. A. Stepanov. International Symposium on Algorithms and Computation (ISAAC), 573-582, 2005.

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

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. ACM Symposium on Principles of Distributed Computing (PODC), 118-125, 2005.

Refined memorisation for vertex cover. L.S. Chandran and F. Grandoni. International Workshop on Parameterized and Exact Computation (IWPEC), 61-70, 2004.

Decremental clique problem. F. Grandoni and G. F. Italiano. International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 142-153, 2004.

Improved algorithms for max-restricted path consistency. F. Grandoni and G. F. Italiano. International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 142-153, 2004.

Other

Exact algorithms for maximum independent set. F. Grandoni. Entry of Encyclopedia of Algorithms, 680-683, 2016.

Exact algorithms for dominating set. F. V. Fomin, F. Grandoni, and D. Kratsch. Entry of Encyclopedia of Algorithms, 2008.

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.

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.

Exact algorithms for hard graph problems. F. Grandoni. Ph.D. Thesis. University of Rome Tor Vergata. 2004.


updated 24th August 2023