Seeun William Umboh

Lecturer in Algorithms
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

Research Interests

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

Sampson Wong, PhD (current, co-supervised with Joachim Gudmundsson)
Jahanvi Khatkar, Honours (current)
Ive Zhang (SSP S2 2019), Max Davy (SSP S1 2019), Qiang Qu (Summer 2019)

Teaching

COMP3027/3927 Algorithm Design (S1 2020, S1 2019)

Program Committees

SOSA 2021, FSTTCS 2018, APPROX 2017

Publications

  • 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
    arXiv
  • Timing Matters: Online Dynamics in Broadcast Games
    Shuchi Chawla, Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh, and Seeun William Umboh
    WINE 2018 / Invited to special issue of ACM Transactions on Economics and Computation (TEAC)
    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
    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 / Invited to special issue of Discrete Mathematics, Algorithms and Applications
    arXiv