# Laura Sanità

## Associate Professor

Department of Mathematics and Computer ScienceEindhoven University of Technology

PO Box 513

5600 MB Eindhoven

**Research Interests:**

Network Design, Approximation Algorithms, Combinatorial Optimization, Operations Research

### Short Bio

July 2003: |
Bachelor's degree in Management Engineering, from "Università di Roma Tor Vergata", Italy. |

October 2005: |
Master's degree in Management Engineering, from "Università di Roma Tor Vergata", Italy. |

January 2009: |
Doctoral degree in Operations Research, from "Università Sapienza di Roma", Rome, Italy. |

February 2009 — August 2011: |
PostDoc at Discrete Optimization Group, EPFL, Lausanne, Switzerland. |

September 2011 — December 2011: |
World Trip (here is my route!) |

January 2012 — June 2017: | Assistant Professor at C&O, University of Waterloo, Canada. |

July 2017 — January 2021: | Associate Professor at C&O, University of Waterloo, Canada. |

...since February 2020: | Associate Professor at TU Eindhoven, Netherlands. |

### Activities

News: | We will organize IPCO 2022 in Eindhoven! We are organizing a Hausdorff Trimester Research Program in “Discrete Optimization” in Fall 2021 -- check for events! Since February 2021, I am also affiliated with the University of Waterloo as an adjunct professor. |

Program Committees: | APPROX 2021 (Chair), MFCS 2021, WADS 2021, CanaDAM 2021, CSR 2021, ESA 2020, APPROX 2020, WAOA 2020, SODA 2020, SODA 2019, FUN 2018, ISAAC 2017, APPROX 2017, SPAA 2017, IPCO 2017, WAOA 2015 (Co-chair), WAOA 2014, ESA 2014. |

Editorship: | Associate Editor of the journals "Mathematical Programming", "Discrete Optimization" and "Operations Research Letters". |

Some awards: | Recipient of a NWO-VIDI award, from the Dutch Research Council, Netherlands. |

Recipient of a 2019 Discovery Accelerator Supplements Award, from the Natural Sciences and Engineering Research Council of Canada (NSERC). | |

Recipient of a UWaterloo Faculty of Mathematics Golden Jubilee Research Excellence Award. | |

Recipient of 2015 Early Researcher Award administered by the Province of Ontario. | |

Co-recipient of the Best Paper Award at the conference STOC 2010. |

### Selected Publications

**Note:**
Colours distinguish
Journals,
Conference Proceedings, or
Others.
On papers authors are listed in alphabetical order.

- Z. K. Koh, L. Sanità,
*Stabilizing weighted graphs*,

Mathematics of Operations Research, Mathematics of Operations Research 45(4), pages 1318-1341, 2020. - Z. K. Koh, L. Sanità,
*An efficient characterization of submodular spanning tree games*,

Mathematical Programming, 183, 1-2, pages 359-377, 2020. - Z. K. Koh, L. Sanità,
*An efficient characterization of submodular spanning tree games*,

IPCO 2019 (20th conference on Integer Programming and Combinatorial Optimization), pages 275-287. - S. Kafer, K. Pashkovich, L. Sanità,
*On the circuit diameter of some combinatorial polytopes*,

Siam Journal on Discrete Mathematics, 33(1): 1-25, 2019. - L. Sanità,
*The diameter of the fractional matching polytope and its hardness implications*,

FOCS 2018 (59th Annual IEEE Symposium on Foundations of Computer Science), pages 910-921. - S. Ahmadian, U. Bhaskar, L. Sanità, C. Swamy,
*Algorithms for Inverse Optimization Problems*,

ESA 2018 (26th Annual European Symposium on Algorithms), pages 1:1-1:14. - Z. K. Koh, L. Sanità,
*Stabilizing weighted graphs*,

ICALP 2018 (45th International Colloquium on Automata, Languages, and Programming), pages 83:1-83:13. - S. Fiorini, M. Gross, J. Koenemann, L. Sanità,
*Approximating Tree Augmentation via Chvatal-Gomory cuts*,

SODA 2018 (29th ACM-SIAM Symposium on Discrete Algorithms), pages 817-831. - S. Ahmadian, H. Hosseinzadeh, L. Sanità,
*Stabilizing network bargaining games by blocking players*,

Mathematical Programming, 172(1): 249-275, 2018. - A. Abdi, R. Fukasawa, L. Sanità,
*Opposite elements in clutters*,

Mathematics of Operations Research, Volume 43, No. 2, pages 428-459, 2018. - G. Guruganesh, J. Iglesias, R Ravi, L. Sanità,
*Single-sink Fractionally Subadditive Network Design*,

ESA 2017 (25th European Symposium on Algorithms), pages 46:1-46:13. - T. Rothvoss, L. Sanità,
*0/1 Polytopes with quadratic Chvatal rank*,

Operations Research, 65(1): 212-220, 2017. - A. Feldmann, J. Koenemann, K. Pashkovich, L. Sanità,
*Fast Approximation Algorithms for the Generalized Survivable Network Design Problem*,

ISAAC 2016 (International symposium on algorithms and computation), pages 33:1-33:12. - S. Ahmadian, H. Hosseinzadeh, L. Sanità,
*Stabilizing network bargaining games by blocking players*,

IPCO 2016 (18th conference on Integer Programming and Combinatorial Optimization), pages 164-177. - A. Feldman, J. Koenemann, N. Olver, L. Sanità,
*On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree*,

Mathematical Programming, Volume 160, pages 379-406, 2016. - A. Abdi, A. Feldmann, B. Guenin, J. Koenemann, L. Sanità,
*Lehman's Theorem and the Directed Steiner Tree Problem*,

SIAM Journal on Discrete Mathematics, Volume 30 Issue 1, pages 141-153, 2016. - G. Guruganesh, L. Sanità, C. Swamy,
*Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems*,

SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms), pages 676-695. - H. Efsandiari, M. Hajiaghayi, J. Koenemann, H. Mahini, D.L. Malec, L. Sanità,
*Approximate Deadline-Scheduling with Precedence Constraints*,

ESA 2015 (23rd European Symposium on Algorithms), pages 483-495. - A. Bock, K. Chandrasekaran, J. Koenemann, B. Peis, L. Sanità,
*Finding small stabilizers for unstable graphs*,

Mathematical Programming, Volume 154, pages 173-196, 2015. - Y. Faenza, L. Sanità,
*On the existence of compact eps-approximated formulations for Knapsack in the original space*,

Operations Research Letters, Volume 43 Issue 3, pages 339-342, 2015. - J. Byrka, A. Karrenbauer, L. Sanità,
*The interval constrained 3-coloring problem*,

Theoretical Computer Science, Volume 593 Issue C, pages 42-50, 2015. - A. Bock, L. Sanità,
*The capacitated orienteering problem*,

Discrete Applied Mathematics, Volume 195, pages 31-42, 2015. - M. Di Summa, D. Pritchard, L. Sanità,
*Finding the closest ultrametric*,

Discrete Applied Mathematics, Volume 180, pages 70-80, 2015. - A. Bock, K. Chandrasekaran, J. Koenemann, B. Peis, L. Sanità,
*Finding small stabilizers for unstable graphs*,

IPCO 2014 (17th Conference on Integer Programming and Combinatorial Optimization), LNCS 8494, pages 150-161, 2014. - A. Feldman, J. Koenemann, N. Olver, L. Sanità,
*On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree*,

APPROX and RANDOM 2014 Proceedings, pages 176-191, 2014. - J. Edmonds, L. Sanità,
*Exponentiality of the exchange algorithm for finding another room-partitioning*,

Discrete Applied Mathematics, Volume 164, Part 1, Pages 86-91, 2014. - J. Koenemann, Sina Sadeghian, L. Sanità,
*An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree*,

FOCS 2013 (54th Annual IEEE Symposium on Foundations of Computer Science). - T. Rothvoss, L. Sanità,
*0/1 Polytopes with quadratic Chvatal rank*,

IPCO 2013 (16th Conference on Integer Programming and Combinatorial Optimization), LNCS Volume 7801, 2013, pages 349-361. - J. Koenemann, S. Sadeghian, L. Sanità,
*Better Approximation Algorithms for Technology Diffusion*,

ESA 2013 (21st European Symposium on Algorithms). - A. Bock, L. Sanità,
*On the approximability of two capacitated vehicle routing problems*,

INOC 2013 (International Network Optimization Conference), ENDS, Volume 41, Pages 519-526. - J. Byrka, F. Grandoni, T. Rothvoss, L. Sanità,
*Steiner Tree approximation via iterative randomized rounding*,

Journal of the ACM, Volume 60 Issue 1, 2013. - N. Haehnle, L. Sanità, R. Zenklusen,
*Stable routing and unique-max coloring on trees*,

Siam Journal on Discrete Mathematics 27(1), pages 109 - 125, 2013. - G. Oriolo, L. Sanità, R. Zenklusen,
*Network design with a discrete set of traffic matrices*,

Operations Research Letters, Volume 41, Issue 4, Pages 390-396, 2013. - A. Bock, E. Grant, J. Koenemann, L. Sanità,
*The School Bus Problem on Trees*,

Algorithmica, Algorithmica 67(1), Pages 49-64, 2013. - A. Bock, E. Grant, J. Koenemann, L. Sanità,
*The School Bus Problem on Trees*,

ISAAC 2011 (22nd International Symposium on Algorithms and Computation). - F. Eisenbrand, N. Kakimura, T. Rothvoss, L. Sanità,
*Set covering with ordered replacement -- Additive and multiplicative gaps*,

IPCO 2011 (15th Conference on Integer Programming and Combinatorial Optimization), LNCS 6655, pages 170-182, 2011. - C. Buchheim, F. Liers, L. Sanità,
*An exact algorithm for robust network design*,

INOC 2011 (International Network Optimization Conference), LNCS 6701, pages 7-17, 2011. - F. Grandoni, T. Rothvoss, L. Sanità,
*From Uncertainty to Non-Linearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk*,

Mathematics of Operations Research, Vol. 36, No. 2, pages 185 - 204, (2011). - J. Byrka, F. Grandoni, T. Rothvoss, L. Sanità,
*An improved LP-based approximation for Steiner Tree*,

STOC 2010 (Proceedings of the 42th ACM Symposium on Theory of Computing), pages 583-592.*Best Paper Award.* - J. Edmonds, L. Sanità,
*On finding another room-partitioning of the vertices*,

ISCO 2010 Proceedings, ENDM 36 (2010), pages 1257-1264. - J. Byrka, A. Karrenbauer, L. Sanità,
*The interval constrained 3-coloring problem*,

LATIN 2010 Proceedings, A. Lopez-Ortiz (Ed.), LNCS 6034, pages 591-602, (2010). - S. Fiorini, G. Oriolo, L. Sanità, D.O. Theis,
*The VPN problem with concave costs*,

Siam Journal on Discrete Mathematics, Volume 24, Issue 3, pages 1080-1090, (2010). - F. Grandoni, G. Nicosia, G. Oriolo, L. Sanità,
*Stable Routing under the Spanning Tree Protocol*,

Operations Research Letters, Volume 38, Issue 5, pages 399-404 (2010). - T. Rothvoss, L. Sanità,
*On the complexity of the asymmetric VPN problem*,

APPROX and RANDOM 2009 Proceedings, Dinur et al. (Eds.), LNCS 5687, pages 326-338, 2009. - P. Iovanna, G. Nicosia, G. Oriolo, L. Sanità, E. Sperduto,
*Local restoration for trees and arborescences*,

FITraMEn 2008 Proceedings, R. Valadas and P. Salvador (Eds.), LNCS 5464, pages 130-140, 2009. - L. Sanità,
*Robust Network Design*,

Ph.D. thesis, Università “Sapienza” di Roma, January 2009. - L. Sanità, G. Oriolo, P. Iovanna, R. Sabella,
*Communication Network*,

Patent, WO2009106153A1 (September 3, 2009) and US20110176438 A1 (July 21, 2011).

### Current students

PhD students- Sean Kafer
- Dylan Hyatt-Denesik

- Charalampos Angelidakis