S. Umboh

Most-cited papers

Nested Convex Bodies are Chaseable
N. Bansal, Martin Böhm, Marek Eliáš, G. Koumoutsos +1 more
2017Algorithmica37 citations Open access
Semantic Scholar
Tight approximation bounds for dominating set on graphs of bounded arboricity
N. Bansal, S. Umboh
2017Information Processing Letters32 citations
Semantic Scholar
Online Network Design Algorithms via Hierarchical Decompositions
S. Umboh
2014ACM-SIAM Symposium on Discrete Algorithms29 citations
Semantic Scholar
Secretary Problems with Convex Costs
Siddharth Barman, S. Umboh, Shuchi Chawla, David L. Malec
2011International Colloquium on Automata, Languages and Programming22 citations
Semantic Scholar
Online Weighted Cardinality Joint Replenishment Problem with Delay
R. Chen, Jahanvi Khatkar, S. Umboh
2022International Colloquium on Automata, Languages and Programming17 citations
Semantic Scholar
The Power of Clairvoyance for Multi-Level Aggregation and Set Cover with Delay
N. Le, S. Umboh, Ningyuan Xie
2023ACM-SIAM Symposium on Discrete Algorithms16 citations
Semantic Scholar
Online Matching with Set and Concave Delays
Lindsey Deryckere, S. Umboh
2022International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques14 citations
Semantic Scholar
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
Y. Bartal, Ora Nova Fandina, S. Umboh
2020ACM-SIAM Symposium on Discrete Algorithms14 citations
Semantic Scholar
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
N. Bansal, Daniel Reichman, S. Umboh
2016ACM-SIAM Symposium on Discrete Algorithms14 citations Open access
Semantic Scholar
LAST but not Least: Online Spanners for Buy-at-Bulk
Anupam Gupta, R. Ravi, Kunal Talwar, S. Umboh
2016ACM-SIAM Symposium on Discrete Algorithms13 citations Open access
Semantic Scholar
A Bicriteria Approximation for the Reordering Buffer Problem
Siddharth Barman, Shuchi Chawla, S. Umboh
2012Embedded Systems and Applications13 citations
Semantic Scholar
Freelance drivers with a decline choice: Dispatch menus in on-demand mobility services for assortment optimization
Yue Yang, S. Umboh, Mohsen Ramezani
2024Transportation Research Part B: Methodological10 citations Open access
Semantic Scholar
Online TCP Acknowledgment under General Delays
S. Bhore, M. Pawlowski, S. Umboh
2026arXiv.org7 citations
Semantic Scholar
Runtime and energy constrained work scheduling for heterogeneous systems
V. Raca, S. Umboh, E. Mehofer, Bernhard Scholz
2022Journal of Supercomputing7 citations
Semantic Scholar
On the Extended TSP Problem
Julián Mestre, S. Pupyrev, S. Umboh
2021International Symposium on Algorithms and Computation7 citations
Semantic Scholar
Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
T. Ezra, Stefano Leonardi, M. Pawlowski, M. Russo +1 more
2024Algorithmica6 citations Open access
Semantic Scholar
Online Computation of String Net Frequency
Peaker Guo, S. Umboh, Anthony Wirth, Justin Zobel
2024SPIRE6 citations
Semantic Scholar
Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
David B. Shmoys, Varun Suriyanarayana, S. Umboh
2026ACM-SIAM Symposium on Discrete Algorithms5 citations Open access
Semantic Scholar
Optimal Dynamic Parameterized Subset Sampling
Jun-Hao Gan, S. Umboh, Hanzhi Wang, Anthony Wirth +1 more
2024Proc. ACM Manag. Data5 citations Open access
Semantic Scholar
Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
Michael Dinitz, Jeremy T. Fineman, S. Umboh
2025International Colloquium on Automata, Languages and Programming4 citations
Semantic Scholar
Tight Bounds for Online Weighted Tree Augmentation
J. Naor, S. Umboh, David P. Williamson
2019Algorithmica4 citations
Semantic Scholar
Online Constrained Forest and Prize-Collecting Network Design
Jiawei Qian, S. Umboh, David P. Williamson
2017Algorithmica4 citations Open access
Semantic Scholar
Colorful Vertex Recoloring of Bipartite Graphs
B. Patt-Shamir, Adi Rosen, S. Umboh
2025Symposium on Theoretical Aspects of Computer Science3 citations
Semantic Scholar
Nested Active-Time Scheduling
Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre +2 more
2022International Symposium on Algorithms and Computation3 citations Open access
Semantic Scholar
Online Matching with Set Delay
Lindsey Deryckere, S. Umboh
2022arXiv.org3 citations Open access
Semantic Scholar
Online Matching with Size-Based and Convex Delays
Jun-Hao Gan, Xiao Sun, S. Umboh
2026arXiv.org2 citations
Semantic Scholar
The Online Broadcast Range-Assignment Problem
M. de Berg, A. Markovic, S. Umboh
2020Algorithmica2 citations Open access
Semantic Scholar
Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
Philip Cervenjak, Jun-Hao Gan, S. Umboh, Anthony Wirth
2024International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques1 citations
Semantic Scholar
Bounded-degree light approximate shortest-path trees in doubling metrics
Joachim Gudmundsson, Julián Mestre, S. Umboh
2021Discrete Applied Mathematics1 citations
Semantic Scholar
Network Design with Coverage Costs
Siddharth Barman, Shuchi Chawla, S. Umboh
2013International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques1 citations
Semantic Scholar
Threshold Rules for Online Sample Selection
E. Bach, Shuchi Chawla, S. Umboh
2010Discret. Math. Algorithms Appl.1 citations Open access
Semantic Scholar
Computing Planning Width: How Hard Is It, Really?
Jiajia Song, S. Umboh, M. Helmert, N. Lipovetzky +1 more
2026Proceedings of the ... International Conference on Automated Planning and Scheduling0 citations Open access
Semantic Scholar
A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
Philip Cervenjak, Jun-Hao Gan, Naonori Kakimura, S. Umboh +1 more
2026Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems0 citations
Semantic Scholar
Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems
Jun-Hao Gan, Xiao Sun, S. Umboh
2026arXiv.org0 citations
Semantic Scholar
Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
Clement Canonne, Yun Li, S. Umboh
2025International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques0 citations
Semantic Scholar
On the Computational Complexity of Partial Satisfaction Planning
Jia-Jia Song, S. Umboh, N. Lipovetzky, Sebastian Sardiña
2025European Conference on Artificial Intelligence0 citations Open access
Semantic Scholar
Optimal bounds on a tree inference algorithm
J. Gardiner, Lachlan L. H. Andrew, Jun-Hao Gan, J. Honorio +1 more
2024arXiv.org0 citations
Semantic Scholar
Timing Matters
Shuchi Chawla, Joseph, Naor, Debmalya Panigrahi +2 more
2016Workshop on Internet and Network Economics0 citations Open access
Semantic Scholar
A 2-Approximation for Redundancy Aware Network Design with Laminar Demands
Siddharth Barman, Shuchi Chawla, S. Umboh
2013arXiv.org0 citations
Semantic Scholar
Advanced Complexity Theory 2 / 18 / 2008 Lecture 11 : Concentration on Influential Variables
D. van Melkebeek, S. Umboh
20080 citations
Semantic Scholar
Lecture 23: Threshold Phenomena 2 Infinite Graphs
D. van Melkebeek, S. Umboh
0 citations
Semantic Scholar