ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 10, 2024
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 full ...
Full textCite
ConferenceProceedings 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleSIAM Journal on Computing · January 1, 2024
The Gomory-Hu tree or cut tree [R. E. Gomory and T. C. Hu, J. Soc. Indust. Appl. Math., 9 (1961), pp. 551-570] 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 ...
Full textCite
ConferenceLeibniz 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 textCite
ConferenceLeibniz 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 textCite
Journal ArticleACM 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 textCite
ConferenceACM 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 textCite
Journal ArticleACM 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 textCite
ConferenceLeibniz 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 textCite
ConferenceProceedings 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
ConferenceProceedings 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
ConferenceProceedings - 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 textCite
ConferenceAdvances 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
Journal ArticleManagement 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 textCite
ConferenceGIS: 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 textCite
ConferenceACM 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 textCite
ConferenceProceedings 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 textCite
ConferenceProceedings 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
ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 10, 2024
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 full ...
Full textCite
ConferenceProceedings 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleSIAM Journal on Computing · January 1, 2024
The Gomory-Hu tree or cut tree [R. E. Gomory and T. C. Hu, J. Soc. Indust. Appl. Math., 9 (1961), pp. 551-570] 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 ...
Full textCite
ConferenceLeibniz 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 textCite
ConferenceLeibniz 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 textCite
Journal ArticleACM 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 textCite
ConferenceACM 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 textCite
Journal ArticleACM 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 textCite
ConferenceLeibniz 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 textCite
ConferenceProceedings 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
ConferenceProceedings 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
ConferenceProceedings - 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 textCite
ConferenceAdvances 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
Journal ArticleManagement 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 textCite
ConferenceGIS: 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 textCite
ConferenceACM 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 textCite
ConferenceProceedings 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 textCite
ConferenceProceedings 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
ConferenceProceedings 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 textCite
Journal ArticleProceedings - 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 textCite
ConferenceProceedings - 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 textCite
ConferenceProceedings - 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 textCite
ConferenceProceedings 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
ConferenceProceedings - 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 textCite
ConferenceProceedings 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
ConferenceAdvances 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
ConferenceAdvances 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
OtherACM 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 textCite
ConferenceLeibniz 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 textCite
ConferenceLeibniz 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 textCite
Journal ArticleProceedings 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 textCite
ConferenceProceedings 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 textCite
ConferenceACM 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 textCite
ConferenceProceedings 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
ConferenceAdvances 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
ConferenceProceedings - 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 textCite
ConferenceProceedings 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 textCite
OtherLeibniz 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 textCite
ConferenceLeibniz 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 textCite
ConferenceLeibniz 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 textCite
Journal ArticleProceedings 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 textCite
Conference37th 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
ConferenceLeibniz 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleSIAM 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 textCite
ConferenceProceedings 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
ConferenceProceedings 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleSIAM 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 textCite
Conference33rd 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
Conference36th 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
ConferenceProceedings 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 textCite
OtherThe 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 textCite
OtherLecture 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleSIAM 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 textCite
ConferenceInternational 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 textCite
ConferenceLeibniz 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 textCite
ConferenceLeibniz 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 textCite
ConferenceProceedings 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 textCite
ConferenceProceedings 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 textCite
ConferenceLeibniz 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleSIAM 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 textCite
Conference31st 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
ConferenceProceedings - 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 textCite
ConferenceEC 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 textCite
ConferenceLecture 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 textCite
ConferenceProceedings - 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 textCite
ConferenceProceedings - 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 textCite
ConferenceAnnual 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 textCite
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 itemCite
ConferenceCIKM 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 textCite
ConferenceLeibniz 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 textCite
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 itemCite
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 itemCite
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 itemCite
ConferenceProceedings 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
