Debmalya Panigrahi

SIAM J. Comput., 2024

Max-Cut with ε-Accurate Predictions.

[BibT_eX]

[DOI]

CoRR, 2024

Hypergraph Unreliability in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Ruoxu Cen

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Poly-logarithmic Competitiveness for the k-Taxi Problem.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Beyond the Quadratic Time Barrier for Network Unreliability.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Universal Algorithms for Clustering Problems.

[BibT_eX]

[DOI]

Arun Ganesh

Bruce M. Maggs

ACM Trans. Algorithms, April, 2023

Robust Algorithms for TSP and Steiner Tree.

[BibT_eX]

[DOI]

Arun Ganesh

Bruce M. Maggs

ACM Trans. Algorithms, April, 2023

Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions.

[BibT_eX]

[DOI]

Kyle Fox

Fred Zhang

ACM Trans. Algorithms, April, 2023

Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422).

[BibT_eX]

[DOI]

Laura Sanità

Dagstuhl Reports, 2023

Online Paging with Heterogeneous Cache Slots.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Near-Linear Time Approximations for Cut Problems via Fair Cuts.

[BibT_eX]

[DOI]

Danupon Nanongkai

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Discrete-Smoothness in Online Algorithms with Predictions.

[BibT_eX]

[DOI]

Noam Touitou

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

A General Framework for Learning-Augmented Online Allocation.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Efficient Algorithms and Hardness Results for the Weighted k-Server Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Pacing Equilibrium in First Price Auction Markets.

[BibT_eX]

[DOI]

Nicolás E. Stier Moses

Eric Sodomka

Christopher A. Wilkens

Manag. Sci., December, 2022

Online Algorithms for Weighted Paging with Predictions.

[BibT_eX]

[DOI]

Zhihao Jiang

Kevin Sun

ACM Trans. Algorithms, 2022

Caching with Time Windows and Delays.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time.

[BibT_eX]

[DOI]

Danupon Nanongkai

CoRR, 2022

Edge connectivity augmentation in near-linear time.

[BibT_eX]

[DOI]

Ruoxu Cen

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Augmenting Edge Connectivity via Isolating Cuts.

[BibT_eX]

[DOI]

Ruoxu Cen

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Online Graph Algorithms with Predictions.

[BibT_eX]

[DOI]

Noam Touitou

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Selectivity Functions of Range Queries are Learnable.

[BibT_eX]

[DOI]

Proceedings of the SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Online Algorithms for the Santa Claus Problem.

[BibT_eX]

[DOI]

Max Springer

MohammadTaghi Hajiaghayi

Mohammad Reza Khani

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions.

[BibT_eX]

[DOI]

Bernardo Subercaseaux

Kevin Sun

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Online Algorithms with Multiple Predictions.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

The pit stop problem: how to plan your next road trip.

[BibT_eX]

[DOI]

Kostas Kollias

Proceedings of the 30th International Conference on Advances in Geographic Information Systems, 2022

Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time.

[BibT_eX]

[DOI]

Ohad Trabelsi

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Learning Influence Adoption in Heterogeneous Networks.

[BibT_eX]

[DOI]

Vincent Conitzer

Hanrui Zhang

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Timing Matters: Online Dynamics in Broadcast Games.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2021

Online Service with Delay.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016).

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Gomory-Hu Tree in Subcubic Time.

[BibT_eX]

[DOI]

Ohad Trabelsi

CoRR, 2021

Approximate Gomory-Hu Tree Is Faster Than n-1 Max-Flows.

[BibT_eX]

[DOI]

CoRR, 2021

Universal Algorithms for Clustering.

[BibT_eX]

[DOI]

Arun Ganesh

Bruce M. Maggs

CoRR, 2021

Minimum Cuts in Directed Graphs via √n Max-Flows.

[BibT_eX]

[DOI]

CoRR, 2021

Approximate Gomory-Hu tree is faster than n - 1 max-flows.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Vertex connectivity in poly-logarithmic max-flows.

[BibT_eX]

[DOI]

Danupon Nanongkai

Sorrachai Yingchareonthawornchai

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Online Combinatorial Auctions.

[BibT_eX]

[DOI]

Yuan Deng

Hanrui Zhang

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Regression Approach to Learning-Augmented Online Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Sparsification of Directed Graphs via Cut Balance.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Minimum Cuts in Directed Graphs via Partial Sparsification.

[BibT_eX]

[DOI]

Kent Quanrud

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Aggregated Deletion Propagation for Counting Conjunctive Query Answers.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2020

Caching with time windows.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Learning Opinions in Social Networks.

[BibT_eX]

[DOI]

Vincent Conitzer

Hanrui Zhang

Proceedings of the 37th International Conference on Machine Learning, 2020

Customizing ML Predictions for Online Algorithms.

[BibT_eX]

[DOI]

Keerti Anand

Rong Ge

Proceedings of the 37th International Conference on Machine Learning, 2020

Online Two-Dimensional Load Balancing.

[BibT_eX]

[DOI]

Sungjin Im

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Deterministic Min-cut in Poly-logarithmic Max-flows.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Tight Bounds for Online Vector Scheduling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

A General Framework for Graph Sparsification.

[BibT_eX]

[DOI]

Wai Shing Fung

Nicholas J. A. Harvey

SIAM J. Comput., 2019

Generalized Deletion Propagation on Counting Conjunctive Query Answers.

[BibT_eX]

[DOI]

Shweta Patwa

Sudeepa Roy

CoRR, 2019

Dynamic set cover: improved algorithms and lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Elastic Caching.

[BibT_eX]

[DOI]

Ravishankar Krishnaswamy

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions.

[BibT_eX]

[DOI]

Kyle Fox

Fred Zhang

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Multi-unit Supply-monotone Auctions with Bayesian Valuations.

[BibT_eX]

[DOI]

Yuan Deng

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Online Algorithms for Rent-Or-Buy with Expert Advice.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Retracting Graphs to Cycles.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

You Get What You Share: Incentives for a Sharing Economy.

[BibT_eX]

[DOI]

Kostas Kollias

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Online Buy-at-Bulk Network Design.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Alina Ene

Ravishankar Krishnaswamy

SIAM J. Comput., 2018

Minimizing Latency in Online Ride and Delivery Services.

[BibT_eX]

[DOI]

Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

Online load balancing on related machines.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Randomized Algorithms for Online Vector Load Balancing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Editorial.

[BibT_eX]

[DOI]

Alexandr Andoni

Marcin Pilipczuk

ACM Trans. Algorithms, 2017

Online Node-weighted Steiner Forest and Extensions via Disk Paintings.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Vahid Liaghat

SIAM J. Comput., 2017

Algorithms and Optimization under Uncertainty (NII Shonan Meeting 2017-5).

[BibT_eX]

[DOI]

Niv Buchbinder

Nikhil R. Devanur

NII Shonan Meet. Rep., 2017

Online and dynamic algorithms for set cover.

[BibT_eX]

[DOI]

Ravishankar Krishnaswamy

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Random Contractions and Sampling for Hypergraph and Hedge Connectivity.

[BibT_eX]

[DOI]

Mohsen Ghaffari

David R. Karger

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Profit Sharing and Efficiency in Utility Games.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Faster Algorithms for the Geometric Transportation Problem.

[BibT_eX]

[DOI]

Pankaj K. Agarwal

Kyle Fox

Kasturi R. Varadarajan

Allen Xiao

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Partitioning Orders in Online Shopping Services.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017

Symmetric Interdiction for Matching Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

The Complexity of Stable Matchings under Substitutable Preferences.

[BibT_eX]

[DOI]

Yuan Deng

Bo Waggoner

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

Online Node-Weighted Problems.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Gomory-Hu Trees.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

On the Price of Stability of Undirected Multicast Games.

[BibT_eX]

[DOI]

Rupert Freeman

Samuel Haney

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Online Budgeted Allocation with General Budgets.

[BibT_eX]

[DOI]

Nathaniel Kell

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Online Algorithms for Covering and Packing Problems with Convex Objectives.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Speed Scaling in the Non-clairvoyant Model.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

2014

Online Algorithms for Machine Minimization.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Konstantin Makarychev

Grigory Yaroslavtsev

CoRR, 2014

Online Covering with Convex Objectives and Applications.

[BibT_eX]

[DOI]

CoRR, 2014

Precedence-Constrained Scheduling of Malleable Jobs with Preemption.

[BibT_eX]

[DOI]

Konstantin Makarychev

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Vahid Liaghat

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Fair Allocation in Online Markets.

[BibT_eX]

[DOI]

Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, 2014

Online Set Cover with Set Requests.

[BibT_eX]

[DOI]

Kshipra Bhawalkar

Proceedings of the Approximation, 2014

2013

Document selection for tiered indexing in commerce search.

[BibT_eX]

[DOI]

Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, 2013

Online Mixed Packing and Covering.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Optimization problems in network connectivity.

[BibT_eX]

[DOI]

PhD thesis, 2012

Online Load Balancing on Unrelated Machines with Startup Costs

[BibT_eX]

[DOI]

CoRR, 2012

Online selection of diverse results.

[BibT_eX]

[DOI]

Proceedings of the Fifth International Conference on Web Search and Web Data Mining, 2012

Online Matching with Stochastic Rewards.

[BibT_eX]

[DOI]

Aranyak Mehta

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Maximum bipartite flow in networks with adaptive channel width.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Result enrichment in commerce search using browse trails.

[BibT_eX]

[DOI]

Proceedings of the Forth International Conference on Web Search and Web Data Mining, 2011

Survivable Network Design Problems in Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Provenance views for module privacy.

[BibT_eX]

[DOI]

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

The Semi-stochastic Ski-rental Problem.

[BibT_eX]

[DOI]

Aleksander Madry

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Online Node-Weighted Steiner Tree and Related Problems.

[BibT_eX]

[DOI]

Joseph Naor

Mohit Singh

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Preserving Module Privacy in Workflow Provenance

[BibT_eX]

[DOI]

CoRR, 2010

A Linear-time Algorithm for Sparsification of Unweighted Graphs

[BibT_eX]

[DOI]

CoRR, 2010

A General Framework for Graph Sparsification

[BibT_eX]

[DOI]

CoRR, 2010

Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

Collaborative Measurements of Upload Speeds in P2P Systems.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

2009

A near-linear time algorithm for constructing a cactus representation of minimum cuts.

[BibT_eX]

[DOI]

David R. Karger

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Brief announcement: collaborative measurement of upload speeds in P2P systems.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

TDMA Scheduling in Long-Distance WiFi Networks.

[BibT_eX]

[DOI]

Bhaskaran Raman

Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

ThunderDome: discovering upload constraints using decentralized bandwidth tournaments.

[BibT_eX]

[DOI]

Proceedings of the 2009 ACM Conference on Emerging Networking Experiments and Technology, 2009

2008

Gomory-Hu Trees.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Minimum Cost Topology Construction for Rural Wireless Mesh Networks.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

Detecting Anomalies Using End-to-End Path Measurements.

[BibT_eX]

[DOI]

K. V. M. Naidu

Rajeev Rastogi

Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

A New Channel Assignment Mechanism for Rural Wireless Mesh Networks.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

2007

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Efficient algorithms for computing all low s-t edge connectivities and related problems.

[BibT_eX]

[DOI]

Telikepalli Kavitha