ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 9, 2026
In a linear combinatorial optimization problem, we are given a family F C 2U of feasible subsets of a ground set U of n elements, and our goal is to find S∗ = argminSeF «w,1S . Traditionally, we are either given the weight vector up-front, or else we are g ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 9, 2026
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph G∗ that is realized by sampling each edge independently with some probability p∈ (0, 1] in a base graph G = (V, E). The algorithm is given the ba ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 9, 2026
We give the first algorithms for fully dynamic set cover with non-trivial worst-case guarantees for both recourse and update time. Specifically, we achieve O(logn) recourse and f· log(n) update time in the worst-case, for both approximation regimes: O(logn ...
Full textCite
ConferenceProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2026
The problem of minimizing the total flow time on a single machine is one of the few problems for which we can give an optimal online algorithm: just schedule the job with the shortest remaining processing time (SRPT). However, this requires knowledge of th ...
Full textCite
ConferenceProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2026
In the online sorting problem, a sequence of n numbers in [0,1] (including {0,1}) have to be inserted in an array of size m ≥ n so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aa ...
Full textCite
ConferenceProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2026
Kleinberg and Mullainathan (2024) recently proposed a formal framework called language generation in the limit and showed that given a sequence of example strings from an unknown target language drawn from any countable collection, an algorithm can correct ...
Full textCite
ConferenceJournal of the ACM · July 25, 2025
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 1974, Aho Hopcroft and Ullman asked if vertex connectivity can be computed in linear ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 15, 2025
Online convex paging (Menache and Singh, 2015; Chiplunkar, Henzinger, Kale, and Vötsch, 2023) models a broad class of cost functions for the classical paging problem. In particular, it naturally captures fairness constraints: e.g., that no specific page (o ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 15, 2025
The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability p. Valiant (1979) showed that this problem is #P-hard; therefore, the best we can hope f ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics Lipics · January 1, 2025
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset S of a univers ...
Full textCite
ConferenceProceedings Annual IEEE Symposium on Foundations of Computer Science Focs · January 1, 2025
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 m1+o(1) time. This improves on the previous best bound of O(nm) for weighted gra ...
Full textCite
ConferenceProceedings Annual IEEE Symposium on Foundations of Computer Science Focs · January 1, 2025
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 va ...
Full textCite
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 2 ...
Full textCite
ConferenceAdvances in Neural Information Processing Systems · January 1, 2024
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- ...
Cite
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
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
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
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 ...
Full textCite
ConferenceProceedings of the ACM SIGMOD International Conference on Management of Data · June 11, 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
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
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
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
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
ConferenceProceedings of Machine Learning Research · 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 sampleefficient lear ...
Cite
ConferenceProceedings of Machine Learning Research · January 1, 2020
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 predic ...
Cite
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 t ...
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 arbi ...
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 ...
Full textCite
ConferenceProceedings of Machine Learning Research · 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 rent-or-buy problem (also called ski rental), and obtain algorithms that pro ...
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 s ...
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
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 ...
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
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
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
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
