Skip to main content

Debmalya Panigrahi

Professor of Computer Science
Computer Science
Campus Box 90129, Durham, NC 27708
308 Research Dr, Campus Box 90129, D203 LSRC Building, Durham, NC 27708

Selected Publications


Poly-logarithmic Competitiveness for the k-Taxi Problem

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 The online k-taxi problem generalizes the k-server problem, requiring servers to move between source-sink pairs in an n-point metric space, and the cost is the overhead incurred. In the deterministic setting, the problem has a lower bound on the competitiv ... Full text Cite

Beyond the Quadratic Time Barrier for Network Unreliability

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running times, eventually leading to a Õ(n2)-time algorithm (Karger, STOC 2020). This ... Full text Cite

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

Conference Leibniz International Proceedings in Informatics, LIPIcs · September 1, 2023 In this paper, we study the weighted k-server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweighted) k-server problem which has a polynomial-time solution using min-cost flo ... Full text Cite

A General Framework for Learning-Augmented Online Allocation

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2023 Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental prob ... Full text Cite

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

Journal Article ACM Transactions on Algorithms · April 15, 2023 On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: • We give an algorithm that runs in Õ(mn2k-2) time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algor ... Full text Cite

Robust Algorithms for TSP and Steiner Tree

Conference ACM Transactions on Algorithms · March 9, 2023 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Universal Algorithms for Clustering Problems

Journal Article ACM Transactions on Algorithms · March 9, 2023 This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers ... Full text Cite

Online Paging with Heterogeneous Cache Slots

Conference Leibniz International Proceedings in Informatics, LIPIcs · March 1, 2023 It is natural to generalize the online k-Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To initiate a systematic study of this generalization, we focus on uniform and star metrics. F ... Full text Cite

Near-Linear Time Approximations for Cut Problems via Fair Cuts

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2023 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, ... Cite

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

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2023 We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose addition makes a given set of terminals τ-connected (for any given τ > 0). The runn ... Cite

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

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2023 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 m1+o(1)-time algorithm for constructing a Gomory-Hu tree ... Full text Cite

Discrete-Smoothness in Online Algorithms with Predictions

Conference Advances in Neural Information Processing Systems · January 1, 2023 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 appr ... Cite

Pacing Equilibrium in First Price Auction Markets

Journal Article Management Science · December 1, 2022 Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregatemetrics of interest to advertisers. On such p ... Full text Cite

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

Conference GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems · November 1, 2022 Many online trip planning and navigation software need to routinely solve the problem of deciding where to take stops during a journey for various services such as refueling (or EV charging), rest stops, food, etc. The goal is to minimize the overhead of t ... Full text Cite

Online Algorithms for Weighted Paging with Predictions

Conference ACM Transactions on Algorithms · October 10, 2022 In this article, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unwe ... Full text Cite

Edge connectivity augmentation in near-linear time

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · September 6, 2022 We give an Õ(m)-time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms and closes the long line of work on these problems. ... Full text Cite

Caching with Time Windows and Delays

Other SIAM Journal on Computing · August 2022 Full text Cite

Learning Influence Adoption in Heterogeneous Networks

Conference Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022 · June 30, 2022 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 indiv ... Cite

Selectivity Functions of Range Queries are Learnable

Conference Proceedings of the ACM SIGMOD International Conference on Management of Data · June 10, 2022 This paper explores the use of machine learning for estimating the selectivity of range queries in database systems. Using classic learning theory for real-valued functions based on shattering dimension, we show that the selectivity function of a range spa ... Full text Cite

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

Journal Article Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2022 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 ... Full text Cite

Poly-logarithmic Competitiveness for the k-Taxi Problem

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 The online k-taxi problem generalizes the k-server problem, requiring servers to move between source-sink pairs in an n-point metric space, and the cost is the overhead incurred. In the deterministic setting, the problem has a lower bound on the competitiv ... Full text Cite

Beyond the Quadratic Time Barrier for Network Unreliability

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running times, eventually leading to a Õ(n2)-time algorithm (Karger, STOC 2020). This ... Full text Cite

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

Conference Leibniz International Proceedings in Informatics, LIPIcs · September 1, 2023 In this paper, we study the weighted k-server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweighted) k-server problem which has a polynomial-time solution using min-cost flo ... Full text Cite

A General Framework for Learning-Augmented Online Allocation

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2023 Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental prob ... Full text Cite

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

Journal Article ACM Transactions on Algorithms · April 15, 2023 On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: • We give an algorithm that runs in Õ(mn2k-2) time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algor ... Full text Cite

Robust Algorithms for TSP and Steiner Tree

Conference ACM Transactions on Algorithms · March 9, 2023 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Universal Algorithms for Clustering Problems

Journal Article ACM Transactions on Algorithms · March 9, 2023 This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers ... Full text Cite

Online Paging with Heterogeneous Cache Slots

Conference Leibniz International Proceedings in Informatics, LIPIcs · March 1, 2023 It is natural to generalize the online k-Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To initiate a systematic study of this generalization, we focus on uniform and star metrics. F ... Full text Cite

Near-Linear Time Approximations for Cut Problems via Fair Cuts

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2023 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, ... Cite

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

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2023 We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose addition makes a given set of terminals τ-connected (for any given τ > 0). The runn ... Cite

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

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2023 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 m1+o(1)-time algorithm for constructing a Gomory-Hu tree ... Full text Cite

Discrete-Smoothness in Online Algorithms with Predictions

Conference Advances in Neural Information Processing Systems · January 1, 2023 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 appr ... Cite

Pacing Equilibrium in First Price Auction Markets

Journal Article Management Science · December 1, 2022 Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregatemetrics of interest to advertisers. On such p ... Full text Cite

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

Conference GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems · November 1, 2022 Many online trip planning and navigation software need to routinely solve the problem of deciding where to take stops during a journey for various services such as refueling (or EV charging), rest stops, food, etc. The goal is to minimize the overhead of t ... Full text Cite

Online Algorithms for Weighted Paging with Predictions

Conference ACM Transactions on Algorithms · October 10, 2022 In this article, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unwe ... Full text Cite

Edge connectivity augmentation in near-linear time

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · September 6, 2022 We give an Õ(m)-time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms and closes the long line of work on these problems. ... Full text Cite

Caching with Time Windows and Delays

Other SIAM Journal on Computing · August 2022 Full text Cite

Learning Influence Adoption in Heterogeneous Networks

Conference Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022 · June 30, 2022 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 indiv ... Cite

Selectivity Functions of Range Queries are Learnable

Conference Proceedings of the ACM SIGMOD International Conference on Management of Data · June 10, 2022 This paper explores the use of machine learning for estimating the selectivity of range queries in database systems. Using classic learning theory for real-valued functions based on shattering dimension, we show that the selectivity function of a range spa ... Full text Cite

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

Journal Article Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2022 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 ... Full text Cite

Minimum Cuts in Directed Graphs via Partial Sparsification

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2022 We give an algorithm to find a minimum cut in an edge-weighted directed graph with n vertices and m edges in tildeO(n\max\{m 2/3}, n\}) time. This improves on the 30 year old bound of tildeO(nm) obtained by Hao and Orlin for this problem. Using similar tec ... Full text Cite

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

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2022 We study the k-server problem with time-windows. In this problem, each request i arrives at some point vi of an n-point metric space at time bi and comes with a deadline ei. One of the k servers must be moved to vi at some time in the interval [bi}, ei] to ... Full text Cite

Augmenting Edge Connectivity via Isolating Cuts

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2022 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 ... Cite

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

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2022 In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all (n/2) 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 m ... Full text Cite

Online Algorithms with Multiple Predictions

Conference Proceedings of Machine Learning Research · January 1, 2022 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 perform ... Cite

Augmenting Online Algorithms with ε-Accurate Predictions

Conference Advances in Neural Information Processing Systems · January 1, 2022 A 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 onlin ... Cite

Online Algorithms for the Santa Claus Problem

Conference Advances in Neural Information Processing Systems · January 1, 2022 The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online versi ... Cite

Online Service with Delay

Other ACM Transactions on Algorithms · August 1, 2021 In this article, 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 there is a server that serves these requests. The goal is to minimize the sum of distance ... Full text Cite

Sparsification of directed graphs via cut balance

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2021 In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected a ... Full text Cite

Universal algorithms for clustering problems

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2021 This paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers su ... Full text Cite

Vertex connectivity in poly-logarithmic max-flows

Journal Article Proceedings of the Annual ACM Symposium on Theory of Computing · June 15, 2021 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 ma ... Full text Cite

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

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 15, 2021 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 u ... Full text Cite

Timing Matters: Online Dynamics in Broadcast Games

Conference ACM Transactions on Economics and Computation · May 1, 2021 This article studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solutio ... Full text Cite

Online combinatorial auctions

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2021 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 s ... Cite

Universal Algorithms for Clustering.

Journal Article CoRR · 2021 Cite

Timing Matters: Online Dynamics in Broadcast Games.

Journal Article ACM Trans. Economics and Comput. · 2021 Full text Cite

A Regression Approach to Learning-Augmented Online Algorithms

Conference Advances in Neural Information Processing Systems · January 1, 2021 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 ... Cite

Deterministic min-cut in poly-logarithmic max-flows

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · November 1, 2020 We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs in time O(m{1+ epsilon}) plus polylog (n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of tilde{O}(m c ... Full text Cite

Caching with time windows

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 8, 2020 We consider the (weighted) Paging with Time Windows problem, which is identical to the classical weighted paging problem but where each page request only needs to be served by a given deadline. This problem arises in many practical applications of online c ... Full text Cite

Robust algorithms for TSP and steiner tree

Other Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2020 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Online algorithms for weighted paging with predictions

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2020 In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweig ... Full text Cite

Online two-dimensional load balancing

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2020 In this paper, we consider the problem of assigning 2-dimensional vector jobs to identical machines online so to minimize the maximum load on any dimension of any machine. For arbitrary number of dimensions d, this problem is known as vector scheduling, an ... Full text Cite

Aggregated deletion propagation for counting conjunctive query answers

Journal Article Proceedings of the VLDB Endowment · January 1, 2020 We investigate the computational complexity of minimizing the source side-effect in order to remove a given number of tuples from the output of a conjunctive query. This is a variant of the well-studied deletion propagation problem, the difference being th ... Full text Cite

Learning Opinions in Social Networks

Conference INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 119 · 2020 Cite

Customizing ML Predictions For Online Algorithms

Conference INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 119 · 2020 Cite

Learning opinions in social networks

Conference 37th International Conference on Machine Learning, ICML 2020 · January 1, 2020 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 lea ... Cite

Retracting graphs to cycles

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2019 We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the ma ... Full text Cite

Dynamic set cover: Improved algorithms and lower bounds

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 23, 2019 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(f2 logn/ε5) (amortized) update time, for any ϵ > 0, where f is the maximum number of sets that an element belongs ... Full text Cite

Pacing Equilibrium in First-Price Auction Markets

Conference Proceedings of the 2019 ACM Conference on Economics and Computation · June 17, 2019 Full text Cite

Tight bounds for online vector scheduling

Journal Article SIAM Journal on Computing · January 1, 2019 Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multidimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network ... Full text Cite

Multi-unit supply-monotone auctions with Bayesian valuations

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019 We design multi-unit auctions for budget-constrained bidders in the Bayesian setting. Our auctions are supply-monotone, which allows the auction to be run online without knowing the number of items in advance, and achieve asymptotic revenue optimality. We ... Cite

Elastic caching

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019 Motivated by applications in cloud computing, we study the classical online caching problem for a cache of variable size, where the algorithm pays a maintenance cost that monotonically increases with cache size. This captures not only the classical setting ... Full text Cite

Minimum cut and minimum k-cut in hypergraphs via branching contractions

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019 On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: • We give an algorithm that runs in Oe mn2k−2 time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algor ... Full text Cite

A general framework for graph sparsification

Journal Article SIAM Journal on Computing · January 1, 2019 We present a general framework for constructing cut sparsifiers in undirected graphs-weighted subgraphs for which every cut has the same weight as the original graph, up to a multiplicative factor of (1 ± ϵ). Using this framework, we simplify, unify, and i ... Full text Cite

You get what you share: Incentives for a sharing economy

Conference 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 · January 1, 2019 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 welfa ... Cite

Online Algorithms for Rent-or-Buy with Expert Advice

Conference INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 97 · 2019 Cite

Online algorithms for rent-or-buy with expert advice

Conference 36th International Conference on Machine Learning, ICML 2019 · January 1, 2019 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 rcnt-or-buy problem (also called ski rental), and obtain algorithms that pro ... Cite

Online load balancing on related machines

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 20, 2018 We give a constant-competitive algorithm for the problem of assigning jobs online to machines with non-uniform speed (called related machines) so as to optimize any ℓq-norm of the machine loads. Previously, such a result was only known for the special case ... Full text Cite

Minimizing latency in online ride and delivery services

Other The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018 · April 10, 2018 Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space ... Full text Cite

Timing matters: Online dynamics in broadcast games

Other Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2018 This paper studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution ... Full text Cite

Randomized Algorithms for Online Vector Load Balancing

Conference SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS · January 1, 2018 Link to item Cite

Randomized algorithms for online vector load balancing

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2018 We study randomized algorithms for the online vector bin packing and vector scheduling problems. For vector bin packing, we achieve a competitive ratio of ~O(d1=B), where d is the number of dimensions and B the size of a bin. This improves the previous bou ... Full text Cite

Online buy-at-bulk network design

Journal Article SIAM Journal on Computing · January 1, 2018 We present the first online algorithms for the nonuniform, 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 ... Full text Cite

Partitioning orders in online shopping services

Conference International Conference on Information and Knowledge Management, Proceedings · November 6, 2017 The rapid growth of the Internet has led to the widespread use of newer and richer models of online shopping and delivery services. erace to efficient large scale on-demand delivery has transformed such services into complex networks of shoppers (typically ... Full text Cite

Partitioning Orders in Online Shopping Services

Conference Proceedings of the 2017 ACM on Conference on Information and Knowledge Management · November 6, 2017 Full text Cite

Profit sharing and efficiency in utility games

Conference Leibniz International Proceedings in Informatics, LIPIcs · September 1, 2017 We study utility games (Vetta, FOCS 2002) where a set of players join teams to produce social utility, and receive individual utility in the form of payments in return. These games have many natural applications in competitive settings such as labor market ... Full text Cite

Symmetric interdiction for matching problems

Conference Leibniz International Proceedings in Informatics, LIPIcs · August 1, 2017 Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates ... Full text Cite

Online and dynamic algorithms for set cover

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 19, 2017 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 m ... Full text Cite

Online service with delay

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 19, 2017 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 ... Full text Cite

Faster algorithms for the geometric transportation problem

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2017 Let R, B C Rd for constant d, be two point sets with |R| + |B| = n, and let λ: R∪B → ℕ such that Σr∈Rλ(r) = Σb∈B λ (b) be demand functions over R and B. Let d(·, ·) be a suitable distance function such as the Lp distance. The transportation problem asks to ... Full text Cite

Editorial

Journal Article ACM Transactions on Algorithms · March 1, 2017 Full text Cite

Random contractions and sampling for hypergraph and hedge connectivity

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2017 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 minim ... Full text Cite

Online node-weighted Steiner forest and extensions via disk paintings

Journal Article SIAM Journal on Computing · January 1, 2017 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 ... Full text Cite

The complexity of stable matchings under substitutable preferences

Conference 31st AAAI Conference on Artificial Intelligence, AAAI 2017 · January 1, 2017 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 ... Cite

Online Algorithms for Covering and Packing Problems with Convex Objectives

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 14, 2016 We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxαRn+f(x) s.t. Ax ≥ 1, where f:Rn+ → R+ is a monotone convex function, and A is an m×n matrix with non-negativ ... Full text Cite

Online budgeted allocation with general budgets

Conference EC 2016 - Proceedings of the 2016 ACM Conference on Economics and Computation · July 21, 2016 We study the online budgeted allocation (also called ADWORDS) problem, where a set of impressions arriving online are allocated to a set of budget-constrained advertisers to maximize revenue. Motivated by connections to Internet advertising, several varian ... Full text Cite

On the price of stability of undirected multicast games

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2016 In multicast network design games, a set of agents choose paths from their source locations to a common sink with the goal of minimizing their individual costs, where the cost of an edge is divided equally among the agents using it. Since the work of Anshe ... Full text Cite

Online Buy-at-Bulk Network Design

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 11, 2015 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 pa ... Full text Cite

Tight Bounds for Online Vector Scheduling

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 11, 2015 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 networ ... Full text Cite

Speed scaling in the non-clairvoyant model

Conference Annual ACM Symposium on Parallelism in Algorithms and Architectures · June 13, 2015 In recent years, there has been a growing interest in speed scaling algorithms, where a set of jobs need to be scheduled on a machine with variable speed so as to optimize the flow-times of the jobs and the energy consumed by the machine. A series of resul ... Full text Cite

Online Covering with Convex Objectives and Applications

Other · December 10, 2014 We give an algorithmic framework for minimizing general convex objectives (that are differentiable and monotone non-decreasing) over a set of covering constraints that arrive online. This substantially extends previous work on online covering for linear ob ... Link to item Cite

Fair allocation in online markets

Conference CIKM 2014 - Proceedings of the 2014 ACM International Conference on Information and Knowledge Management · November 3, 2014 A key characteristic of a successful online market is the large participation of agents (producers and consumers) on both sides of the market. While there has been a long line of impressive work on understanding such markets in terms of revenue maximizing ... Full text Cite

Online set cover with set requests

Conference Leibniz International Proceedings in Informatics, LIPIcs · September 1, 2014 We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd so ... Full text Cite

Online Algorithms for Machine Minimization

Other · March 3, 2014 In this paper, we consider the online version of the machine minimization problem (introduced by Chuzhoy et al., FOCS 2004), where the goal is to schedule a set of jobs with release times, deadlines, and processing lengths on a minimum number of identical ... Link to item Cite

Online Load Balancing on Unrelated Machines with Startup Costs

Other · March 20, 2012 Motivated by applications in energy-efficient scheduling in data centers, Khuller, Li, and Saha introduced the {\em machine activation} problem as a generalization of the classical optimization problems of set cover and load balancing on unrelated machines ... Link to item Cite

A Linear-time Algorithm for Sparsification of Unweighted Graphs

Other · May 5, 2010 Given an undirected graph $G$ and an error parameter $\epsilon > 0$, the {\em graph sparsification} problem requires sampling edges in $G$ and giving the sampled edges appropriate weights to obtain a sparse graph $G_{\epsilon}$ with the following property: ... Link to item Cite

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

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2007 Given an undirected unweighted graph G = (V,E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m ... Cite

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

Conference STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING · January 1, 2007 Link to item Cite