# Laura Sanità

## Associate Professor

Combinatorics & Optimization DepartmentUniversity of Waterloo

200 University Ave. W

Waterloo, Ontario

Canada, N2L 3G1

Room: MC 5034

**Phone**: (519) 888-4567 x 31395

**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. |

November 2005 — January 2009: |
Ph.D. student in Operations Research, "Università Sapienza di Roma", Italy. |

May 2007 — July 2007: |
Adonet position at "Institut für Informatik, Universität zu Köln", Cologne, Germany. |

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

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

### News

- Recipient of 2015 Early Researcher Award administered by the Province of Ontario.
- Associate Editor of the journals "Discrete Optimization" and "Operations Research Letters".
- Program Committee services: PC member of SODA 2019, FUN 2018, ISAAC 2017, APPROX 2017, SPAA 2017, IPCO 2017, WAOA 2015 (Co-chair), WAOA 2014, ESA 2014.

### Publications

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

- S. Ahmadian, H. Hosseinzadeh, L. Sanità,
*Stabilizing network bargaining games by blocking players*,

Mathematical Programming, to appear. - L. Sanità,
*The diameter of the fractional matching polytope and its hardness implications*,

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

ESA 2018 (26th Annual European Symposium on Algorithms), to appear. - 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. - 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. - P. Iovanna, G. Oriolo, R. Sabella, L. Sanità,
*Fine protection of data paths in multi-layer network based on the GMPLS paradigm*,

Optical Switching and Networking, 5, pages 159- 169, 2008. - P. Iovanna, G. Oriolo, R. Sabella, L. Sanità,
*Communication Network*,

Patent, Pub. No: WO/2009/106153.

### Teaching (UWaterloo)

Winter 2018

**CO 250: **"Introduction to Optimization".

**CO 750: **"Approximation Algorithms".

Winter 2017

**CO 370: **"Deterministic OR Models".

**CO 750: **"Approximation Algorithms".

Winter 2015

**CO 370: **"Deterministic OR Models".

**CO 250: **"Introduction to Optimization".

Fall 2014

**CO 370: **"Deterministic OR Models".

Winter 2014

**CO 754: **"Approximation Algorithms".

Fall 2013

**CO 450 - CO 650: **"Combinatorial Optimization".

Spring 2013

**CO 250: **"Introduction to Optimization".

Fall 2012

**CO 450 - CO 650: **"Combinatorial Optimization".

Spring 2012

**CO 250: **"Introduction to Optimization".

### Current Students

Grad students- Sean Kafer (PhD student)

- Zhuan Khye Koh (since Fall 2017)

### Past Students

Master's students- Matthew Buckley (graduated in 2018)
- Sean Kafer (graduated in 2017)
- Zhuan Khye Koh (graduated in 2017)
- Charupriya Sharma (graduated in 2017)
- Arash Haddadan (graduated in 2015)
- Jason Liu (graduated in 2014) -- co-supervised with S. Dimitrov
- Sina Sadeghian (graduated in 2013) -- co-supervised with J. Koenemann

- Felix Bauckholt (Summer 2017)
- Cynthia Huang (Summer 2015)
- Miaolan Xie (Summer 2013)
- Guru Guruganesh (Summer and Fall 2012)

- Hamideh Hosseinzadeh (visiting PhD student in Winter 2014)
- Adrian Bock (visiting PhD student in Spring 2012)