Debmalya Panigrahi

NeurIPS Conference 2025 Conference Paper

A Learning-Augmented Approach to Online Allocation Problems

• Ilan Cohen
• Debmalya Panigrahi

In online allocation problems, an algorithm must choose from a set of options at each step, where each option incurs a set of costs/rewards associated with a set of $d$ agents. The goal is to minimize/maximize a function of the accumulated costs/rewards assigned to the agents over the course of the entire allocation process. Such problems are common in combinatorial optimization, including minimization problems such as machine scheduling and network routing, as well as maximization problems such as fair allocation for welfare maximization. In this paper, we develop a general learning-augmented algorithmic framework for online allocation problems that produces a nearly optimal solution using only a single $d$-dimensional vector of learned weights. Using this general framework, we derive learning-augmented online algorithms for a broad range of application problems in routing, scheduling, and fair allocation. Our main tool is convex programming duality, which may also have further implications for learning-augmented algorithms in the future.

FOCS Conference 2025 Conference Paper

Deterministic Almost-Linear-Time Gomory-Hu Trees

• Amir Abboud
• Rasmus Kyng
• Jason Li 0006
• Debmalya Panigrahi
• Maximilian Probst Gutenberg
• Thatchaphol Saranurak
• Weixuan Yuan
• Wuwei Yuan

Given an undirected, weighted graph $G=(V, E, w)$, a Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a tree T over the vertex set V such that for every pair of vertices $s, t \in V$, the ($s, t$) min-cut in T is also an ($s, t$) min-cut in G and has the same value. In this article, we give the first deterministic almost-linear-time algorithm for constructing a Gomory-Hu tree. Our algorithm runs in $m^{1+o(1)}$-time, where m denotes the number of edges in the input graph G; this is clearly optimal up to the $m^{o(1)}$ term in the running time. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $n m^{1+o(1)}$ time using current maxflow algorithms. In fact, our algorithm is also the first almost-linear-time deterministic algorithm for even simpler problems, such as finding the k-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs min-cuts problem to the single-source min-cuts problem incurring only sub-polynomial overhead, and - a deterministic almost-linear time algorithm for the singlesource min-cuts problem.

FOCS Conference 2025 Conference Paper

Fast Algorithms for Graph Arboricity and Related Problems

• Ruoxu Cen
• Henry L. Fleischmann
• George Zhaoqi Li
• Jason Li 0006
• Debmalya Panigrahi

We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m^{1+o(1)}$ time. This improves on the previous best bound of $\tilde{O}(nm)$ for weighted graphs and $\tilde{O}\left(\mathrm{~m}^{3/2}\right)$ for unweighted graphs (Gabow 1995) for this problem. The running time of our algorithm is dominated by a logarithmic number of calls to a directed global minimum cut subroutine – if the running time of the latter problem improves to $m^{1+o(1)}$ (thereby matching the running time of maximum flow), the running time of our arboricity algorithm would improve further to $m^{1+o(1)}$. We also give a new algorithm for computing the entire cut hierarchy – laminar multiway cuts with minimum cut ratio in recursively defined induced subgraphs – in $m n^{1+o(1)}$ time. The cut hierarchy yields the ideal edge loads (Thorup 2001) in a fractional spanning tree packing of the graph which, we show, also corresponds to a max-entropy solution in the spanning tree polytope. For the cut hierarchy problem, the previous best bound was $\tilde{O}\left(n^{2} m\right)$ for weighted graphs and $\tilde{O}\left(n m^{3/2}\right)$ for unweighted graphs.

NeurIPS Conference 2025 Conference Paper

Learning-Augmented Algorithms for $k$-median via Online Learning

• Anish Hebbar
• Rong Ge
• Amit Kumar
• Debmalya Panigrahi

The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

STOC Conference 2025 Conference Paper

Network Unreliability in Almost-Linear Time

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

STOC Conference 2025 Conference Paper

Tight Results for Online Convex Paging

• Anupam Gupta 0001
• Amit Kumar 0001
• Debmalya Panigrahi

SODA Conference 2024 Conference Paper

Beyond the Quadratic Time Barrier for Network Unreliability

• Ruoxu Cen
• William He
• Jason Li 0006
• Debmalya Panigrahi

STOC Conference 2024 Conference Paper

Hypergraph Unreliability in Quasi-Polynomial Time

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank). In this paper, we give quasi-polynomial time approximation schemes for the hypergraph unreliability problem. For any fixed ε ∈ (0, 1), we first give a (1+ε)-approximation algorithm that runs in m O (log n ) time on an m -hyperedge, n -vertex hypergraph. Then, we improve the running time to m · n O (log 2 n ) with an additional exponentially small additive term in the approximation.

NeurIPS Conference 2024 Conference Paper

Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems

• Vincent Cohen-Addad
• Tommaso d'Orsi
• Anupam Gupta
• Euiwoong Lee
• Debmalya Panigrahi

In recent years, there has been a surge of interest in the use of machine-learned predictions to bypass worst-case lower bounds for classical problems in combinatorial optimization. So far, the focus has mostly been on online algorithms, where information-theoretic barriers are overcome using predictions about the unknown future. In this paper, we consider the complementary question of using learned information to overcome computational barriers in the form of approximation hardness of polynomial-time algorithms for NP-hard (offline) problems. We show that noisy predictions about the optimal solution can be used to break classical hardness results for maximization problems such as the max-cut problem and more generally, maximization versions of constraint satisfaction problems (CSPs).

SODA Conference 2024 Conference Paper

Poly-logarithmic Competitiveness for the k -Taxi Problem

• Anupam Gupta 0001
• Amit Kumar 0001
• Debmalya Panigrahi

FOCS Conference 2023 Conference Paper

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

• Amir Abboud
• Jason Li 0006
• Debmalya Panigrahi
• Thatchaphol Saranurak

A Gomory-Hu tree (also called a cut tree) succinctly represents $(s, t)$ min-cuts (and therefore, $(s, t)$ max-flow values) of all pairs of vertices $s, t$ in an undirected graph. In this paper, we give an $m^{1+o(1)}$-time algorithm for constructing a Gomory-Hu tree for a graph with m edges. This shows that the all-pairs max-flows problem has the same running time as the single-pair max-flow problem, up to a subpolynomial factor. Prior to our work, the best known Gomory-Hu tree algorithm was obtained in recent work by Abboud et al. (FOCS 2022) and requires $\tilde{O}\left(n^{2}\right)$ time for a graph with n vertices. Our result marks a natural culmination of over 60 years of research into the all-pairs maxflows problem that started with Gomory and Hu’s pathbreaking result introducing the Gomory-Hu tree in 1961.

NeurIPS Conference 2023 Conference Paper

Discrete-Smoothness in Online Algorithms with Predictions

• Yossi Azar
• Debmalya Panigrahi
• Noam Touitou

In recent years, there has been an increasing focus on designing online algorithms with (machine-learned) predictions. The ideal learning-augmented algorithm is comparable to the optimum when given perfect predictions (consistency), to the best online approximation for arbitrary predictions (robustness), and should interpolate between these extremes as a smooth function of the prediction error. In this paper, we quantify these guarantees in terms of a general property that we call discrete-smoothness, and achieve discrete-smooth algorithms for online covering, specifically the facility location and set cover problems. For set cover, our work improves the results of Bamas, Maggiori, and Svensson (2020) by augmenting consistency and robustness with smoothness guarantees. For facility location, our work improves on prior work by Almanza et al. (2021) by generalizing to nonuniform costs and also providing smoothness guarantees by augmenting consistency and robustness.

SODA Conference 2023 Conference Paper

Near-Linear Time Approximations for Cut Problems via Fair Cuts

• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak

We introduce the notion of fair cuts as an approach to leverage approximate ( s, t )-mincut (equivalently ( s, t )-maxflow) algorithms in undirected graphs to obtain near-linear time approximation algorithms for several cut problems. Informally, for any α ≥ 1, an α-fair ( s, t )-cut is an ( s, t )-cut such that there exists an ( s, t )-flow that uses 1/α fraction of the capacity of every edge in the cut. (So, any α-fair cut is also an α-approximate mincut, but not vice-versa.) We give an algorithm for (1 + ε)-fair ( s, t )-cut in Õ ( m )-time, thereby matching the best runtime for (1 + ε)-approximate ( s, t )-mincut [Peng, SODA '16]. We then demonstrate the power of this approach by showing that this result almost immediately leads to several applications: • the first nearly-linear time (1 + ε)-approximation algorithm that computes all-pairs maxflow values (by constructing an approximate Gomory-Hu tree). Prior to our work, such a result was not known even for the special case of Steiner mincut [Dinitz and Vainstein, STOC '94; Cole and Hariharan, STOC '03]; • the first almost-linear-work subpolynomial-depth parallel algorithms for computing (1+ε)-approximations for all-pairs maxflow values (again via an approximate Gomory-Hu tree) in unweighted graphs; • the first near-linear time expander decomposition algorithm that works even when the expansion parameter is polynomially small; this subsumes previous incomparable algorithms [Nanongkai and Saranurak, FOCS '17; Wulff-Nilsen, FOCS '17; Saranurak and Wang, SODA '19]. * The full version of the paper can be accessed at https: //arxiv. org/abs/2203. 00751

SODA Conference 2023 Conference Paper

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

• Ruoxu Cen
• William He
• Jason Li 0006
• Debmalya Panigrahi

SODA Conference 2022 Conference Paper

Augmenting Edge Connectivity via Isolating Cuts

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS ‘20). Our algorithm uses poly-logarithmic calls to any max-flow algorithm, which yields a running time of Õ ( m + n 3/2 ) and improves on the previous best time of Õ ( n 2 ) (Benczúr and Karger, SODA ‘98) for this problem. We also obtain an identical improvement in the running time of the closely related edge splitting off problem in undirected graphs.

NeurIPS Conference 2022 Conference Paper

Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions

• Anupam Gupta
• Debmalya Panigrahi
• Bernardo Subercaseaux
• Kevin Sun

The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an $O(\log(1/\varepsilon))$-competitive algorithm for caching, and a simple $O(1/\varepsilon)$-competitive algorithm for a large family of covering problems, including set cover and facility location, with $\epsilon$-accurate predictions.

FOCS Conference 2022 Conference Paper

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

• Amir Abboud
• Robert Krauthgamer
• Jason Li 0006
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Ohad Trabelsi

In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all $\begin{pmatrix}n\\2\end{pmatrix}$ pairs of vertices in an undirected graph can be solved using only $n-1$ calls to any (single-pair) max-flow algorithm. Even assuming a linear-time max-flow algorithm, this yields a running time of $O(mn)$, which is $O(n^{3})$ when $m=\Theta(n^{2})$. While subsequent work has improved this bound for various special graph classes, no subcubic-time algorithm has been obtained in the last 60 years for general graphs. We break this longstanding barrier by giving an $\tilde{O}(n^{2})$-time algorithm on general, integer-weighted graphs. Combined with a popular complexity assumption, we establish a counter-intuitive separation: all-pairs max-flows are strictly easier to compute than all-pairs shortest-paths. Our algorithm produces a cut-equivalent tree, known as the Gomory-Hu tree, from which the max-flow value for any pair can be retrieved in near-constant time. For unweighted graphs, we refine our techniques further to produce a Gomory-Hu tree in the time of a poly-logarithmic number of calls to any maxflow algorithm. This shows an equivalence between the all-pairs and single-pair max-flow problems, and is optimal up to polylogarithmic factors. Using the recently announced $m^{1+o(1)}$-time max-flow algorithm (Chen et al. , March 2022), our Gomory-Hu tree algorithm for unweighted graphs also runs in $m^{1+o(1)}$-time.

STOC Conference 2022 Conference Paper

Edge connectivity augmentation in near-linear time

• Ruoxu Cen
• Jason Li 0006
• Debmalya Panigrahi

AAAI Conference 2022 Conference Paper

Learning Influence Adoption in Heterogeneous Networks

• Vincent Conitzer
• Debmalya Panigrahi
• Hanrui Zhang

We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each individual node by sampling only a small number of nodes and observing/testing their states. We study this problem in heterogeneous networks, in which each individual node has a set of distinct features that determine how it is affected by the propagating entity. We give an efficient algorithm with nearly optimal sample complexity for two variants of this learning problem, corresponding to symptomatic and asymptomatic spread. In each case, the optimal sample complexity naturally generalizes both the complexity of learning how nodes are affected in isolation, and the complexity of learning influence adoption in a homogeneous network.

NeurIPS Conference 2022 Conference Paper

Online Algorithms for the Santa Claus Problem

• Max Springer
• MohammadTaghi Hajiaghayi
• Debmalya Panigrahi
• Mohammad Khani

The Santa Claus problem is a fundamental problem in {\em fair division}: the goal is to partition a set of {\em heterogeneous} items among {\em heterogeneous} agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order is random, then for $n$ agents and any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $\Omega(\log n / \varepsilon^2)$ to every agent (assuming each item has at most unit value). We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even for random arrival order.

ICML Conference 2022 Conference Paper

Online Algorithms with Multiple Predictions

• Keerti Anand
• Rong Ge 0001
• Amit Kumar 0001
• Debmalya Panigrahi

This paper studies online algorithms augmented with multiple machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.

SODA Conference 2022 Conference Paper

Online Graph Algorithms with Predictions

• Yossi Azar
• Debmalya Panigrahi
• Noam Touitou

FOCS Conference 2021 Conference Paper

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

• Anupam Gupta 0001
• Amit Kumar 0001
• Debmalya Panigrahi

We study the $k$ -server problem with time-windows. In this problem, each request $i$ arrives at some point $v_{i}$ of an $n$ -point metric space at time $b_{i}$ and comes with a deadline $e_{i}$. One of the $k$ servers must be moved to $v_{i}$ at some time in the interval [ $b_{i}, e_{i}$ ] to satisfy this request. We give an online algorithm for this problem with a competitive ratio of $\text{poly}\log(n, \Delta)$, where $\Delta$ is the aspect ratio of the metric space. Prior to our work, the best competitive ratio known for this problem was $O(k\ \text{poly}\log(n))$ given by Azar et al. (STOC 2017). Our algorithm is based on a new covering linear program relaxation for $k$ -server on HSTs. This LP naturally corresponds to the min-cost flow formulation of $k$ -server, and easily extends to the case of time-windows. We give an online algorithm for obtaining a feasible fractional solution for this LP, and a primal dual analysis framework for accounting the cost of the solution. Together, they yield a new $k$ -server algorithm with poly-logarithmic competitive ratio, and extend to the time-windows case as well. Our principal technical contribution lies in thinking of the covering LP as yielding a truncated covering LP at each internal node of the tree, which allows us to keep account of server movements across subtrees. We hope that this LP relaxation and the algorithm/analysis will be a useful tool for addressing $k$ -server and related problems.

FOCS Conference 2021 Conference Paper

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

• Jason Li 0006
• Debmalya Panigrahi
• Thatchaphol Saranurak

We give an $n^{2+o(1)}$ -time algorithm for finding $s-t$ min-cuts for all pairs of vertices $s$ and $t$ in a simple, undirected graph on $n$ vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of $\tilde{O}(n^{2. 5})$ by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of $n$.

NeurIPS Conference 2021 Conference Paper

A Regression Approach to Learning-Augmented Online Algorithms

• Keerti Anand
• Rong Ge
• Amit Kumar
• Debmalya Panigrahi

The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since these parameters are, in general, real-valued functions, a natural approach is to use regression techniques to make these predictions. We introduce this approach in this paper, and explore it in the context of a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem, thereby diverging from the use of off-the-shelf regression tools with standard bounds on statistical error.

STOC Conference 2021 Conference Paper

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

• Jason Li 0006
• Debmalya Panigrahi

The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting s − t mincuts (and by duality, the values of s − t maxflows) for all pairs of vertices s and t in an undirected graph. Gomory and Hu showed that it can be computed using n −1 exact maxflow computations. Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50 years later, even for approximate mincuts. In this paper, we break this longstanding barrier and give an algorithm for computing a (1+є)-approximate Gomory-Hu tree using log( n ) maxflow computations. Specifically, we obtain the runtime bounds we describe below. We obtain a randomized (Monte Carlo) algorithm for undirected, weighted graphs that runs in Õ( m + n 3/2 ) time and returns a (1+є)-approximate Gomory-Hu tree algorithm whp. Previously, the best running time known was Õ( n 5/2 ), which is obtained by running Gomory and Hu’s original algorithm on a cut sparsifier of the graph. Next, we obtain a randomized (Monte Carlo) algorithm for undirected, unweighted graphs that runs in m 4/3+ o (1) time and returns a (1+є)-approximate Gomory-Hu tree algorithm whp. This improves on our first result for sparse graphs, namely m = o ( n 9/8 ). Previously, the best running time known for unweighted graphs was Õ( mn ) for an exact Gomory-Hu tree (Bhalgat et al. , STOC 2007); no better result was known if approximations are allowed. As a consequence of our Gomory-Hu tree algorithms, we also solve the (1+є)-approximate all pairs mincut and single source mincut problems in the same time bounds. (These problems are simpler in that the goal is to only return the s − t mincut values, and not the mincuts.) This improves on the recent algorithm for these problems in Õ( n 2 ) time due to Abboud et al. (FOCS 2020).

FOCS Conference 2021 Conference Paper

Minimum Cuts in Directed Graphs via Partial Sparsification

• Ruoxu Cen
• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Kent Quanrud

We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tilde{O}(n\cdot\max\{m^{2/3}, \ n\})$ time. This improves on the 30 year old bound of $\tilde{O}(nm)$ obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain $\tilde{O}(n^{2}/\epsilon^{2})$ -time $(1+{\epsilon})$ -approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed $\epsilon$. Before our work, no (1 + $\epsilon)$ -approximation algorithm better than the exact runtime of $\tilde{O}(nm)$ is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to $\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$ calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

SODA Conference 2021 Conference Paper

Online Combinatorial Auctions

• Yuan Deng
• Debmalya Panigrahi
• Hanrui Zhang 0001

We study combinatorial auctions in online environments with the goal of maximizing social welfare. In this problem, new items become available on each day and must be sold before their respective expiration dates. We design online auctions for the widely studied classes of submodular and XOS valuations, and show the following results: – For submodular valuations, we give an O (log m )-competitive mechanism for adversarial valuations and an O (1)-competitive mechanism for Bayesian valuations, where m is the total number of items. Both these mechanisms are computationally efficient and universally truthful for myopic agents, i. e. , agents with no knowledge of the future. – For XOS valuations, we show that there is no online mechanism that can achieve a competitive ratio of o (( m/ log m ) 1/3 ) even in a Bayesian setting. Our lower bound holds even if we do not require truthfulness and/or computational efficiency of the mechanism. This establishes a sharp separation between XOS valuations and its subclass of submodular valuations for online combinatorial auctions. In contrast, no such separation exists for offline auctions, where the best bounds for both submodular and XOS valuations are O ((log log m ) 3 ) for adversarial settings (Assadi and Singla, FOCS 2019) and O (1) for Bayesian settings (Dütting et al. , FOCS 2017). In contrast to the above, if items do not expire and only need to be sold before the market closes, then we give a reduction from offline to online mechanisms that preserves the competitive ratio for all subadditive valuations (that includes XOS and submodular valuations), thereby achieving the same bounds as the respective best offline mechanisms.

STOC Conference 2021 Conference Paper

Vertex connectivity in poly-logarithmic max-flows

• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Sorrachai Yingchareonthawornchai

The vertex connectivity of an m -edge n -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in ( m α ) time for any α ≥ 1, if there is a m α -time maxflow algorithm. Using the current best maxflow algorithm that runs in m 4/3+ o (1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m 4/3+ o (1) -time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ( mn )-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o ( mn ) running time was known before our work, even if we assume an ( m )-time maxflow algorithm. Our new technique is robust enough to also improve the best Õ( mn )-time bound for directed vertex connectivity to mn 1−1/12+ o (1) time

STOC Conference 2020 Conference Paper

Caching with time windows

• Anupam Gupta 0001
• Amit Kumar 0001
• Debmalya Panigrahi

ICML Conference 2020 Conference Paper

Customizing ML Predictions for Online Algorithms

• Keerti Anand
• Rong Ge 0001
• Debmalya Panigrahi

A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.

FOCS Conference 2020 Conference Paper

Deterministic Min-cut in Poly-logarithmic Max-flows

• Jason Li 0006
• Debmalya Panigrahi

We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs in time O(m 1+ε ) plus polylog ( n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of ~O(m·min(√m, n 2/3 )) for weighted graphs, and m 4/3+o(1) for unweighted (multi)-graphs. This is the first improvement in the running time of deterministic algorithms for the min-cut problem on general (weighted/multi) graphs since the early 1990s when a running time bound of ~O(mn) was established for this problem.

ICML Conference 2020 Conference Paper

Learning Opinions in Social Networks

• Vincent Conitzer
• Debmalya Panigrahi
• Hanrui Zhang 0001

We study the problem of learning opinions in social networks. The learner observes the states of some sample nodes from a social network, and tries to infer the states of other nodes, based on the structure of the network. We show that sample-efficient learning is impossible when the network exhibits strong noise, and give a polynomial-time algorithm for the problem with nearly optimal sample complexity when the network is sufficiently stable.

STOC Conference 2019 Conference Paper

Dynamic set cover: improved algorithms and lower bounds

• Amir Abboud
• Raghavendra Addanki
• Fabrizio Grandoni 0001
• Debmalya Panigrahi
• Barna Saha

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1+є) f -approximation for fully dynamic set cover in O ( f 2 log n /є 5 ) (amortized) update time, for any є > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O ( f 2 /є 5 ), while still obtaining an (1+є) f -approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O ( f 2 ) in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on f is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of O ( f 1−є ) must have an approximation factor that is Ω( n δ ) for some constant δ>0 under the Strong Exponential Time Hypothesis.

SODA Conference 2019 Conference Paper

Elastic Caching

• Anupam Gupta 0001
• Ravishankar Krishnaswamy
• Amit Kumar 0001
• Debmalya Panigrahi

SODA Conference 2019 Conference Paper

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

• Kyle Fox
• Debmalya Panigrahi
• Fred Zhang

SODA Conference 2019 Conference Paper

Multi-unit Supply-monotone Auctions with Bayesian Valuations

• Yuan Deng
• Debmalya Panigrahi

ICML Conference 2019 Conference Paper

Online Algorithms for Rent-Or-Buy with Expert Advice

• Sreenivas Gollapudi
• Debmalya Panigrahi

We study the use of predictions by multiple experts (such as machine learning algorithms) to improve the performance of online algorithms. In particular, we consider the classical rent-or-buy problem (also called ski rental), and obtain algorithms that provably improve their performance over the adversarial scenario by using these predictions. We also prove matching lower bounds to show that our algorithms are the best possible, and perform experiments to empirically validate their performance in practice

AAAI Conference 2019 Conference Paper

You Get What You Share: Incentives for a Sharing Economy

• Sreenivas Gollapudi
• Kostas Kollias
• Debmalya Panigrahi

In recent years, a range of online applications have facilitated resource sharing among users, resulting in a significant increase in resource utilization. In all such applications, sharing one’s resources or skills with other agents increases social welfare. In general, each agent will look for other agents whose available resources complement hers, thereby forming natural sharing groups. In this paper, we study settings where a large population self-organizes into sharing groups. In many cases, centralized optimization approaches for creating an optimal partition of the user population are infeasible because either the central authority does not have the necessary information to compute an optimal partition, or it does not have the power to enforce a partition. Instead, the central authority puts in place an incentive structure in the form of a utility sharing method, before letting the participants form the sharing groups by themselves. We first analyze a simple equal-sharing method, which is the one most typically encountered in practice and show that it can lead to highly inefficient equilibria. We then propose a Shapley-sharing method and show that it significantly improves overall social welfare.

STOC Conference 2018 Conference Paper

Online load balancing on related machines

• Sungjin Im
• Nathaniel Kell
• Debmalya Panigrahi
• Maryam Shadloo

In this paper, we consider the problem of assigning jobs online to machines with non-uniform speeds (also called related machines ) so to optimize a given norm of the machine loads. A long line of work, starting with the seminal work of Graham in the 1960s, has led to tight competitive ratios for all ℓ q norms for two scenarios: the special case of identical machines (uniform machine speeds) and the more general setting of unrelated machines (jobs have arbitrary processing times on machines). For non-uniform machine speeds, however, the only known result was a constant competitive competitive ratio for the makespan (ℓ ∞ ) norm, via the so-called slowest-fit algorithm (Aspnes, Azar, Fiat, Plotkin, and Waarts, JACM ’97). Our first result in this paper is to obtain the first constant-competitive algorithm for scheduling on related machines for any arbitrary ℓ q norm . Recent literature has further expanded the scope of this problem to vector scheduling , to capture multi-dimensional resource requirements in applications such as data centers. As in the scalar case, tight bounds are known for vector scheduling on identical and unrelated machines. Our second set of results is to give tight competitive ratios for vector scheduling on related machines for the makespan and all ℓ q norms . No previous bounds were known, even for the makespan norm, for related machines. We employ a convex relaxation of the ℓ q -norm objective and use a continuous greedy algorithm to solve this convex program online. To round the fractional solution, we then use a novel restructuring of the instance that we call machine smoothing . This is a generic tool that reduces a problem on related machines to a set of problem instances on identical machines, and we hope it will be useful in other settings with non-uniform machine speeds as well.

SODA Conference 2018 Conference Paper

Randomized Algorithms for Online Vector Load Balancing

• Yossi Azar
• Ilan Reuven Cohen
• Debmalya Panigrahi

STOC Conference 2017 Conference Paper

Online and dynamic algorithms for set cover

• Anupam Gupta 0001
• Ravishankar Krishnaswamy
• Amit Kumar 0001
• Debmalya Panigrahi

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offline algorithms for set cover. The former leads to a competitive ratio of O (log n t ), where n t is the number of currently active elements at timestep t , while the latter yields competitive ratios dependent on f t , the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

STOC Conference 2017 Conference Paper

Online service with delay

• Yossi Azar
• Arun Ganesh
• Rong Ge 0001
• Debmalya Panigrahi

In this paper, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, that has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm . The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to k > 1 servers, and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.

SODA Conference 2017 Conference Paper

Random Contractions and Sampling for Hypergraph and Hedge Connectivity

• Mohsen Ghaffari 0001
• David R. Karger
• Debmalya Panigrahi

We initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. We give a polynomial-time approximation scheme and a quasi-polynomial exact algorithm for hedge connectivity. This provides strong evidence that the hedge connectivity problem is tractable, which contrasts with prior work that established the intractability of the corresponding s-t min-cut problem. Our techniques also yield new combinatorial and algorithmic results in hypergraph connectivity. Next, we study the behavior of hedge graphs under uniform random sampling of hedges. We show that unlike graphs, all cuts in the sample do not converge to their expected value in hedge graphs. Nevertheless, the min-cut of the sample does indeed concentrate around the expected value of the original min-cut. This leads to a sharp threshold on hedge survival probabilities for graph disconnection. To the best of our knowledge, this is the first network reliability analysis under dependent edge failures.

AAAI Conference 2017 Conference Paper

The Complexity of Stable Matchings under Substitutable Preferences

• Yuan Deng
• Debmalya Panigrahi
• Bo Waggoner

In various matching market settings, such as hospital-doctor matching markets (Hatfield and Milgrom 2005), the existence of stable outcomes depends on substitutability of preferences. But can these stable matchings be computed efficiently, as in the one-to-one matching case? The algorithm of (Hatfield and Milgrom 2005) requires efficient implementation of a choice function over substitutable preferences. We show that even given efficient access to a value oracle or preference relation satisfying substitutability, exponentially many queries may be required in the worst case to implement a choice function. Indeed, this extends to examples where a stable matching requires exponential time to compute. We characterize the computational complexity of stable matchings by showing that efficient computation of a choice function is equivalent to efficient verification—determining whether or not, for a given set, the most preferred subset is the entire set itself. Clearly, verification is necessary for computation, but we show that it is also sufficient: specifically, given a verifier, we design a polynomial-time algorithm for computing a choice function, implying an efficient algorithm for stable matching. We then show that a verifier can be implemented efficiently for various classes of functions, such as submodular functions, implying efficient stable matching algorithms for a broad range of settings. We also investigate the effect of ties in the preference order, which causes complications both in defining substitutes and in computation. In this case, we tightly connect the computational complexity of the choice function to a measure on the number of ties.

FOCS Conference 2016 Conference Paper

Online Algorithms for Covering and Packing Problems with Convex Objectives

• Yossi Azar
• Niv Buchbinder
• T. -H. Hubert Chan
• Shahar Chen
• Ilan Reuven Cohen
• Anupam Gupta 0001
• Zhiyi Huang 0002
• Ning Kang 0001

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: min xϵ R + n f(x) s. t. Ax ≥ 1, where f: R + n → R + is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: max yϵR+ m Σ j=1 m yj - g(A T y), where g: R + n →R + is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

FOCS Conference 2015 Conference Paper

Online Buy-at-Bulk Network Design

• Alina Ene
• Deeparnab Chakrabarty
• Ravishankar Krishnaswamy
• Debmalya Panigrahi

We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show: 1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs. 2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs. 3. For any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of O̅(k {1/2+ε} polylog(n)) (where k is the number of demands) for MC-BB in directed graphs. 4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al. , FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.

FOCS Conference 2015 Conference Paper

Tight Bounds for Online Vector Scheduling

• Sungjin Im
• Nathaniel Kell
• Janardhan Kulkarni
• Debmalya Panigrahi

Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and L r norms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and L r -norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations - for all L r norms and in both the identical and unrelated machines settings. Our main results are: · For identical machines, we show that the optimal competitive ratio is Θ(log d/ log log d) by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general L r norms. · For unrelated machines, we show that the optimal competitive ratio is Θ(log m + log d) by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general L r norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual L r objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.

SODA Conference 2013 Conference Paper

Online Mixed Packing and Covering

• Yossi Azar
• Umang Bhaskar
• Lisa Fleischer
• Debmalya Panigrahi

FOCS Conference 2013 Conference Paper

Online Node-Weighted Steiner Forest and Extensions via Disk Paintings

• MohammadTaghi Hajiaghayi
• Vahid Liaghat
• Debmalya Panigrahi

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e. g. , planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online 0, 1-proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

FOCS Conference 2012 Conference Paper

Online Matching with Stochastic Rewards

• Aranyak Mehta
• Debmalya Panigrahi

The online matching problem has received significant attention in recent years because of its connections to allocation problems in Internet advertising, crowd-sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations, rather it is to maximize the number of successful allocations, where success of an allocation is governed by a stochastic process which follows the allocation. To address such applications, we propose and study the online matching problem with stochastic rewards (called the ONLINE STOCHASTIC MATCHING problem) in this paper. Our problem also has close connections to the existing literature on stochastic packing problems, in fact, our work initiates the study of online stochastic packing problems. We give a deterministic algorithm for the ONLINE STOCHASTIC MATCHING problem whose competitive ratio converges to (approximately) 0. 567 for uniform and vanishing probabilities. We also give a randomized algorithm which outperforms the deterministic algorithm for higher probabilities. Finally, we complement our algorithms by giving an upper bound on the competitive ratio of any algorithm for this problem. This result shows that the best achievable competitive ratio for the ONLINE STOCHASTIC MATCHING problem is provably worse than that for the (non-stochastic) online matching problem.

STOC Conference 2011 Conference Paper

A general framework for graph sparsification

• Wai Shing Fung
• Ramesh Hariharan
• Nicholas J. A. Harvey
• Debmalya Panigrahi

TCS Journal 2011 Journal Article

Maximum bipartite flow in networks with adaptive channel width

• Yossi Azar
• Aleksander Mądry
• Thomas Moscibroda
• Debmalya Panigrahi
• Aravind Srinivasan

FOCS Conference 2011 Conference Paper

Online Node-Weighted Steiner Tree and Related Problems

• Joseph Naor
• Debmalya Panigrahi
• Mohit Singh

We obtain the first online algorithms for the node-weighted Steiner tree, Steiner forest and group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm for the Steiner tree problem runs in polynomial time, while those for the other two problems take quasi-polynomial time. Our algorithms can be viewed as online LP rounding algorithms in the framework of Buchbinder and Naor (Foundations and Trends in Theoretical Computer Science, 2009); however, while the natural LP formulation of these problems do lead to fractional algorithms with a poly-logarithmic competitive ratio, we are unable to round these LPs online without losing a polynomial factor. Therefore, we design new LP formulations for these problems drawing on a combination of paradigms such as spider decompositions, low-depth Steiner trees, generalized group Steiner problems, etc. and use the additional structure provided by these to round the more sophisticated LPs losing only a poly-logarithmic factor in the competitive ratio. As further applications of our techniques, we also design polynomial-time online algorithms with poly-logarithmic competitive ratios for two fundamental network design problems in edge-weighted graphs: the group Steiner forest problem (thereby resolving an open question raised by Chekuri et. al. (SODA 2008)) and the single source ℓ-vertex connectivity problem (which complements similar results for the corresponding edge-connectivity problem due to Gupta et. al. (STOC 2009)).

SODA Conference 2011 Conference Paper

Survivable Network Design Problems in Wireless Networks

• Debmalya Panigrahi

SODA Conference 2009 Conference Paper

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

• David R. Karger
• Debmalya Panigrahi

SODA Conference 2008 Conference Paper

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

• Anand Bhalgat
• Ramesh Hariharan
• Telikepalli Kavitha
• Debmalya Panigrahi

STOC Conference 2007 Conference Paper

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

• Ramesh Hariharan
• Telikepalli Kavitha
• Debmalya Panigrahi
• Anand Bhalgat

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn). All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s -t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n 20/9 ) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n 20/9 n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

SODA Conference 2007 Conference Paper

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

• Ramesh Hariharan
• Telikepalli Kavitha
• Debmalya Panigrahi