Seeun William Umboh

Lecturer in Algorithms and CS Honours Coordinator
School of Computer Science
The University of Sydney

Email: william DOT umboh AT sydney DOT edu DOT au
Office: Room 410, Building J12, School of Computer Science
Phone: +61 2 8627 7122

About Me

I am a Lecturer in Algorithms and the CS Honours Coordinator in the School of Computer Science at the University of Sydney. Previously, I was a postdoc with Prof. Nikhil Bansal at TU Eindhoven. I received my Ph.D. in Computer Science from the University of Wisconsin-Madison where I was co-advised by Profs. Shuchi Chawla and Eric Bach. I also have a M.Sc in Computer Science and a B.Sc. majoring in Computer Science and Mathematics, all from UW-Madison.

I am broadly interested in theoretical computer science and combinatorial optimization. Currently, I am working on approximation and online algorithms, graph optimization (e.g. network design, graph partitioning), and metric embeddings.

Advising

PhD: Lindsey Deryckere (current); Sampson Wong, (current, co-supervised with Joachim Gudmundsson)
MPhil: Sampson Wong (2019, co-supervised with Joachim Gudmundsson)
Honours: Alan Wu, Faye Xie, Tom Schwarz
Past Honours students: Ryder Chen (2021, First Class Honours with University Medal), Mai Le (2021, First Class Honours with University Medal), Ive Zhang (2021, First Class Honours with University Medal), Jahanvi Khatkar (2020, First Class Honours with University Medal)
Interns: Tanishq Dubey (2021), Aryan Gupta (2020), Finn Waugh (Winter 2020), TJ Kojima (Summer 2020), Qiang Qu (Summer 2019)
SSP: Ryder Chen (S2 2020), Cameron Eggins (S2 2020), Ive Zhang (S2 2019), Max Davy (S1 2019)

Teaching

COMP3027/3927 Algorithm Design (S1 2022, S1 2021, S1 2020, S1 2019)
COMP9123 Data Structures and Algorithms (S1 2022 (co-taught with Clement Canonne))

Program Committees

WAOA 2022, LATIN 2022, APPROX 2022, SODA 2022, SOSA 2021, FSTTCS 2018, APPROX 2017

Publications

  • Runtime and Energy Constrained Work Scheduling for Heterogeneous Systems
    Valon Raca, Seeun William Umboh, Eduard Mehofer, and Bernhard Scholz
    Journal of Supercomputing, 2022
  • Online Weighted Cardinality Joint Replenishment Problem with Delay
    Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh
    ICALP 2022
  • On the Extended TSP Problem
    Julian Mestre, Sergey Pupyrev, and Seeun William Umboh
    ISAAC 2021
  • Bounded-Degree Light Approximate Shortest Path Trees in Doubling Metrics
    Joachim Gudmundsson, Julian Mestre, and Seeun William Umboh
    Discrete Mathematics and Applications, 2021
  • The Online Broadcast Range-Assignment Problem
    Mark de Berg, Aleksandar Markovic, and Seeun William Umboh
    ISAAC 2020
  • Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
    Yair Bartal, Nova Fandina, and Seeun William Umboh
    SODA 2020
  • Tight Bounds for Online Weighted Tree Augmentation
    Joseph (Seffi) Naor, Seeun William Umboh, and David P. Williamson
    ICALP 2019 / Algorithmica, 2021
    arXiv
  • Timing Matters: Online Dynamics in Broadcast Games
    Shuchi Chawla, Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh, and Seeun William Umboh
    WINE 2018 / Special issue of ACM Transactions on Economics and Computation (TEAC) for WINE 2018
    arXiv
  • Online Constrained Forest and Prize-Collecting Network Design
    Jiawei Qian, Seeun William Umboh, and David P. Williamson
    Algorithmica, 2018
    DOI / arXiv
  • Nested Convex Bodies Are Chaseable
    Nikhil Bansal, Martin Bohm, Marek Elias, Grigorios Koumoutsos, and Seeun William Umboh
    SODA 2018 / Algorithmica, 2020
    arXiv
  • Tight Approximation Bounds for Dominating Set on Graphs of Bounded Arboricity
    Nikhil Bansal and Seeun William Umboh
    Information Processing Letters, 2017
    DOI
  • LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
    Nikhil Bansal, Daniel Reichman, and Seeun William Umboh
    SODA 2017
    arXiv
  • LAST but not Least: Online Spanners for Buy-at-Bulk
    Anupam Gupta, R. Ravi, Kunal Talwar, and Seeun William Umboh
    SODA 2017
    arXiv
  • Online Network Design Algorithms via Hierarchical Decompositions
    Seeun Umboh
    SODA 2015
    arXiv
  • Network Design with Coverage Costs
    Siddharth Barman, Shuchi Chawla, and Seeun Umboh
    APPROX 2014
    proceedings / slides (APPROX14) / video (Fields Institute)
  • A Bicriteria Approximation for the Reordering Buffer Problem
    Siddharth Barman, Shuchi Chawla, and Seeun Umboh
    ESA 2012
    arXiv
  • Secretary Problems with Convex Costs
    Siddharth Barman, Seeun Umboh, Shuchi Chawla, and David Malec
    ICALP 2012
    arXiv / poster
  • Threshold Rules for Sample Selection
    Eric Bach, Shuchi Chawla, and Seeun Umboh
    COCOON 2010 / Special issue of Discrete Mathematics, Algorithms and Applications for COCOON 2010
    arXiv