Kent Quanrud

SODA Conference 2025 Conference Paper

Faster single-source shortest paths with negative real weights via proper hop distance

• Yufan Huang
• Peter Jin
• Kent Quanrud

SODA Conference 2024 Conference Paper

Adaptive Out-Orientations with Applications

• Chandra Chekuri
• Aleksander Bjørn Grodt Christiansen
• Jacob Holm
• Ivor van der Hoog
• Kent Quanrud
• Eva Rotenberg
• Chris Schwiegelshohn

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out- degree is proportional to the arboricity α of the graph, in, either, an amortised update time of 𝒪 (log 2 n log α), or a worst-case update time of 𝒪 (log 3 n log α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either 𝒪 (log n log α), amortised, or 𝒪 (log 2 n log α), worst-case, for the problem of maintaining an edge-orientation with at most 𝒪 (α + log n ) out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work: Firstly, we obtain deterministic algorithms for maintaining a (1 + ɛ) approximation of the maximum subgraph density, ρ, of the dynamic graph. Our algorithms have update times of 𝒪 (ɛ -6 log 3 n log ρ) worst- case, and 𝒪 (ɛ -4 log 2 n log ρ) amortised, respectively. We may output a subgraph H of the input graph where its density is a (1 + ɛ) approximation of the maximum subgraph density in time linear in the size of the subgraph. These algorithms have improved update time compared to the 𝒪 (ɛ -6 log 4 n ) algorithm by Sawlani and Wang from STOC 2020. Secondly, we obtain an 𝒪 (ɛ -6 log 3 n log α) worst-case update time algorithm for maintaining a (1 + ɛ)OPT + 2 approximation of the optimal out-orientation of a graph with adaptive arboricity α, improving the 𝒪(ɛ -6 α 2 log 3 n ) algorithm by Christiansen and Rotenberg from ICALP 2022. This yields the first worst-case polylogarithmic dynamic algorithm for decomposing into 𝒪 (α) forests. Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a variety of problems including maximal matching, Δ + 1 colouring, and matrix vector multiplication. All update times are worst- case 𝒪 (α + log 2 n log α), where α is the current arboricity of the graph. For the maximal matching problem, the state-of-the-art deterministic algorithms by Kopelowitz, Krauthgamer, Porat, and Solomon from ICALP 2014 runs in time 𝒪( α 2 + log 2 n ), and by Neiman and Solomon from STOC 2013 runs in time. We give improved running times whenever the arboricity. * The full version of the paper can be accessed at https: //arxiv. org/abs/2310. 18146

SODA Conference 2024 Conference Paper

Faster exact and approximation algorithms for packing and covering matroids via push-relabel

• Kent Quanrud

Matroids are a fundamental object of study in combinatorial optimization. Three closely related and important problems involving matroids are maximizing the size of the union of k independent sets (that is, k-fold matroid union), computing k disjoint bases (a. k. a. matroid base packing), and covering the elements by k bases (a. k. a. matroid base covering). These problems generalize naturally to integral and real-valued capacities on the elements. This work develops faster exact and/or approximation problems for these and some other closely related problems such as optimal reinforcement and matroid membership. We obtain improved running times both for general matroids in the independence oracle model and for the graphic matroid. The main thrust of our improvements comes from developing a faster and unifying push-relabel algorithm for the integer-capacitated versions of these problems, building on previous work by Frank and Miklós [24]. We then build on this algorithm in two directions. First we develop a faster augmenting path subroutine for k -fold matroid union that, when appended to an approximation version of the push-relabel algorithm, gives a faster exact algorithm for some parameters of k. In particular we obtain a subquadratic-query running time in the uncapacitated setting for the three basic problems listed above. We also obtain faster approximation algorithms for these problems with real-valued capacities by reducing to small integral capacities via randomized rounding. To this end, we develop a new randomized rounding technique for base covering problems in matroids that may also be of independent interest.

SODA Conference 2024 Conference Paper

Quotient sparsification for submodular functions

• Kent Quanrud

Graph sparsification has been an important topic with many structural and algorithmic consequences. Recently hypergraph sparsification has come to the fore and has seen exciting progress. In this paper we take a fresh perspective and show that they can be both be derived as corollaries of a general theorem on sparsifying matroids and monotone submodular functions. Quotients of matroids and monotone submodular functions generalize k -cuts in graphs and hypergraphs. We show that a weighted ground set of a monotone submodular function f can be sparsified while approximately preserving the weight of every quotient of f with high probability in randomized polynomial time. This theorem conceptually unifies cut sparsifiers for undirected graphs [7] with other interesting applications. One basic application is to reduce the number of elements in a matroid while preserving the weight of every quotient of the matroid. For hypergraphs, the theorem gives an alternative approach to the hypergraph cut sparsifiers obtained recently in [12], that also preserves all k -cuts. Another application is to reduce the number of points in a set system while preserving the weight of the union of every collection of sets. We also present algorithms that sparsify hypergraphs and set systems in nearly linear time, and sparsify matroids in nearly linear time and queries in the rank oracle model. * Dept. of Computer Science, Purdue University, West Lafayette, IN 47907. Supported in part by NSF grant CCF-2129816.

SODA Conference 2022 Conference Paper

Densest Subgraph: Supermodularity, Iterative Peeling, and Flow

• Chandra Chekuri
• Kent Quanrud
• Manuel R. Torres

NeurIPS Conference 2022 Conference Paper

Faster and Scalable Algorithms for Densest Subgraph and Decomposition

• Elfarouk Harb
• Kent Quanrud
• Chandra Chekuri

We study the densest subgraph problem (DSG) and the densest subgraph local decomposition problem (DSG-LD) in undirected graphs. We also consider supermodular generalizations of these problems. For large scale graphs simple iterative algorithms perform much better in practice than theoretically fast algorithms based on network-flow or LP solvers. Boob et al [1] recently gave a fast iterative algorithm called Greedy++ for DSG. It was shown in [2] that it converges to a $(1-\epsilon)$ relative approximation to the optimum density in $O(\frac{1}{\epsilon^2} \frac{\Delta(G)}{\lambda^*})$ iterations where $\Delta(G)$ is the maximum degree and $\lambda^*$ is the optimum density. Danisch et al. [3] gave an iterative algorithm based on the Frank-Wolfe algorithm for DSG-LD that takes $O(\frac{m\Delta(G) }{\epsilon^2})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector $\hat{b}$, where $m$ is number of edges in the graph. In this paper we give a new iterative algorithm for both problems that takes at most $O(\frac{\sqrt{m\Delta(G)}}{\epsilon})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector; each iteration can be implemented in $O(m)$ time. We describe a fractional peeling technique which has strong empirical performance as well as theoretical guarantees. The algorithm is scalable and simple, and can be applied to graphs with hundreds of millions of edges. We test our algorithm on real and synthetic data sets and show that it provides a significant benefit over previous algorithms. The algorithm and analysis extends to hypergraphs.

FOCS Conference 2021 Conference Paper

Minimum Cuts in Directed Graphs via Partial Sparsification

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

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

SODA Conference 2021 Conference Paper

Spectral Sparsification of Metrics and Kernels

• Kent Quanrud

A set of n points in a geometric space implicitly induces a complete graph where the weight of an edge between two points is a function of the distance between the endpoints. There are many natural problems that arise from such a geometric graph and many standard geometric problems can be recast as simple properties of this graph. A basic algorithmic obstacle that arises is that the explicit size of the graph is quadratic in the size of the input. There is a long line of research overcoming this obstacle in low-dimensional spaces, as well as some positive results in high-dimensional and more abstract models for specific applications. Here we consider graph problems in general and address the issue of constructing the geometric graph. Rather than constructing these graphs exactly, we ask if it is possible to explicitly construct a sparse approximation of these geometric graphs in nearly linear time. We consider geometric graphs where the edge weights are given as either as a metric (via an oracle), or given by a smooth kernel function in a Euclidean space. For both of these settings, we show that for any ∊ > 0, one can compute an explicit (1 + ∊ )-approximate spectral approximation of the geometric graph with Õ ( n/∊ 2 ) edges in Õ ( n/∊ 2 ) randomized time. Some of these algorithms are extremely simple. Composed with nearly linear time graph algorithms, this allows for a broad class of applications on geometric graphs with running times proportional to the number of points.

SODA Conference 2020 Conference Paper

Computing Circle Packing Representations of Planar Graphs

• Sally Dong
• Yin Tat Lee
• Kent Quanrud

SODA Conference 2020 Conference Paper

Fast LP-based Approximations for Geometric Packing and Covering Problems

• Chandra Chekuri
• Sariel Har-Peled
• Kent Quanrud

We derive fast approximation schemes for LP relaxations of several well-studied geometric optimization problems that include packing, covering, and mixed packing and covering constraints. Previous work in computational geometry concentrated mainly on the rounding stage to prove approximation bounds, assuming that the underlying LPs can be solved efficiently. This work demonstrates that many of those results can be made to run in nearly linear time. In contrast to prior work on this topic our algorithms handle weights and capacities, side constraints, and also apply to mixed packing and covering problems, in a unified fashion. Our framework relies crucially on the properties of a randomized MWU algorithm of [41]; we demonstrate that it is well-suited for range spaces that admit efficient approximate dynamic data structures for emptiness oracles. Our framework cleanly separates the MWU algorithm for solving the LP from the key geometric data structure primitives, and this enables us to handle side constraints in a simple way. Combined with rounding algorithms that can also be implemented efficiently, we obtain the first near-linear constant factor approximation algorithms for several problems.

SODA Conference 2019 Conference Paper

On Approximating (Sparse) Covering Integer Programs

• Chandra Chekuri
• Kent Quanrud

We consider approximation algorithms for covering integer programs of the form min 〈 c, x 〉 over x ∊ ℤ ≥0 n s. t. Ax ≥ b and x ≤ d; where A ∊ ℝ ≥0 m × n, b ∊ ℝ ≥0 m, and c, d ∊ ℝ ≥0 n all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x < d as CIP ∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP ∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP ∞.

STOC Conference 2019 Conference Paper

Parallelizing greedy for submodular set function maximization in matroids and beyond

• Chandra Chekuri
• Kent Quanrud

We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints. An important open problem is the classical setting of matroid constraint, which has been instrumental for developments in submodular function maximization. In this paper we develop a general strategy to parallelize the well-studied greedy algorithm and use it to obtain a randomized (1 / 2 − є)-approximation in O( log 2 ( n ) / 2 ) rounds of adaptivity. We rely on this algorithm, and an elegant amplification approach due to Badanidiyuru and Vondrák to obtain a fractional solution that yields a near-optimal randomized ( 1 − 1/ e − є )-approximation in O( log 2 ( n ) / є 3 ) rounds of adaptivity. For non-negative functions we obtain a ( 3−2√2 − є )-approximation and a fractional solution that yields a ( 1 / e − є)-approximation. Our approach for parallelizing greedy yields approximations for intersections of matroids and matchoids, and the approximation ratios are comparable to those known for sequential greedy.

SODA Conference 2019 Conference Paper

Submodular Function Maximization in Parallel via the Multilinear Relaxation

• Chandra Chekuri
• Kent Quanrud

Balkanski and Singer [4] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Subsequent improvements for this problem by Balkanski, Rubinstein, and Singer [6] and Ene and Nguyen [21] resulted in a near-optimal (1 – 1/ e – ∊ )-approximation in O (log n / ∊ 2 ) rounds of adaptivity. Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to packing constraints. Formally our problem is to maximize F ( x ) over x ∊ [0, 1] n subject to where F is the multilinear relaxation of a monotone submodular function. Our algorithm achieves a near-optimal (1 – 1/ e – ∊ )-approximation in O (log 2 m log n / ∊ 4 ) rounds where n is the cardinality of the ground set and m is the number of packing constraints. For many constraints of interest, the resulting fractional solution can be rounded via known randomized rounding schemes that are oblivious to the specific submodular function. We thus derive randomized algorithms with poly-logarithmic adaptivity for a number of constraints including partition and laminar matroids, matchings, knapsack constraints, and their intersections. Our algorithm takes a continuous view point and combines several ideas ranging from the continuous greedy algorithm of [38, 13], its adaptation to the MWU framework for packing constraints [20], and parallel algorithms for packing LPs [31, 41]. For the basic setting of cardinality constraints, this viewpoint gives rise to an alternative, simple to understand algorithm that matches recent results [6, 21]. Our algorithm to solve the multilinear relaxation is deterministic if it is given access to a value oracle for the multilinear extension and its gradient; this is possible in some interesting cases such as the coverage function of an explicitly given set system.

SODA Conference 2018 Conference Paper

Randomized MWU for Positive LPs

• Chandra Chekuri
• Kent Quanrud

We describe and analyze a simple randomized multiplicative weight update (MWU) based algorithm for approximately solving positive linear programming problems, in particular, mixed packing and covering LPs. Given m explicit linear packing and covering constraints over n variables specified by N nonzero entries, Young [36] gave a deterministic algorithm returning an (1 + ε )-approximate feasible solution (if a feasible solution exists) in Õ ( N / ε 2 ) time. We show that a simple randomized implementation matches this bound, and that randomization can be further exploited to improve the running time to Õ ( N / ε + m / ε 2 + n / ε 3 ) (both with high probability). For instances that are not very sparse (with at least ῶ(1/ ε ) nonzeroes per column on average), this improves the running time of Õ ( N / ε 2 ). The randomized algorithm also gives improved running times for some implicitly defined problems that arise in combinatorial and geometric optimization.

FOCS Conference 2017 Conference Paper

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time

• Chandra Chekuri
• Kent Quanrud

We give a nearly linear-time randomized approximation scheme for the Held-Karp bound [22] for Metric-TSP. Formally, given an undirected edge-weighted graph G = (V, ε) on m edges and ε > 0, the algorithm outputs in O(m log 4 n/ε 2 ) time, with high probability, a (1 + ε)-approximation to the Held-Karp bound on the Metric-TSP instance induced by the shortest path metric on G. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the O(m 2 log 2 (m)/ε 2 ) running time achieved previously by Garg and Khandekar.

SODA Conference 2017 Conference Paper

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems

• Chandra Chekuri
• Kent Quanrud

We consider several implicit fractional packing problems and obtain faster implementations of approximation schemes based on multiplicative-weight updates. This leads to new algorithms with near-linear running times for some fundamental problems in combinatorial optimization. We highlight two concrete applications. The first is to find the maximum fractional packing of spanning trees in a capacitated graph; we obtain a (1 - ∊)-approximation in Õ (m/∊ 2 ) time, where m is the number of edges in the graph. Second, we consider the LP relaxation of the weighted unsplittable flow problem on a path and obtain a (1 - ∊)-approximation in O ( n /∊ 2 ) time, where n is the number of demands.

SODA Conference 2016 Conference Paper

A Fast Approximation for Maximum Weight Matroid Intersection

• Chandra Chekuri
• Kent Quanrud

We present an approximation algorithm for the maximum weight matroid intersection problem in the independence oracle model. Given two matroids defined over a common ground set N of n elements, let k be the rank of the matroid intersection and let Q denote the cost of an independence query for either matroid. An exact algorithm for finding a maximum cardinality independent set (the unweighted case), due to Cunningham, runs in O ( nk 1. 5 Q ) time. For the weighted case, algorithms due to Frank and Brezovec et al. run in O ( nk 2 Q ) time. There are also scaling based algorithms that run in time, where W is the maximum weight (assuming all weights are integers), and ellipsoid-style algorithms that run in O (( n 2 log( n )Q + n 3 polylog( n ))log( nW )) time. Recently, Huang, Kakimura, and Kamiyama described an algorithm that gives a (1 – ∊)-approximation for the weighted matroid intersection problem in O ( nk 1. 5 log( k ) Q /∊) time. We observe that a (1 – ∊)-approximation for the maximum cardinality case can be obtained in O ( nkQ /∊) time by terminating Cunningham's algorithm early. Our main contribution is a (1 – ∊) approximation algorithm for the weighted matroid intersection problem with running time O ( nk log 2 (1/∊) Q /∊ 2 ).

NeurIPS Conference 2015 Conference Paper

Online Learning with Adversarial Delays

• Kent Quanrud
• Daniel Khashabi

We study the performance of standard online learning algorithms when the feedback is delayed by an adversary. We show that \texttt{online-gradient-descent} and \texttt{follow-the-perturbed-leader} achieve regret $O(\sqrt{D})$ in the delayed setting, where $D$ is the sum of delays of each round's feedback. This bound collapses to an optimal $O(\sqrt{T})$ bound in the usual setting of no delays (where $D = T$). Our main contribution is to show that standard algorithms for online learning already have simple regret bounds in the most general setting of delayed feedback, making adjustments to the analysis and not to the algorithms themselves. Our results help affirm and clarify the success of recent algorithms in optimization and machine learning that operate in a delayed feedback model.