Scholarly Works - Journal articles
Journal article
Journal of the ACM
·
July 24, 2025
We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on n vertices and m edges using polylog(n) calls to a black box maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this marks ...
Full text
Cite
Journal article
Algorithmica
·
January 1, 2025
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 date, only a few special cases of this problem have been studied. The objective of the work ...
Full text
Cite
Journal article
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
·
January 1, 2025
Cite
Journal article
SIAM 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 text
Cite
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
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
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
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
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
Journal article
CoRR
·
2021
Cite
Journal article
CoRR
·
2021
Cite
Journal article
ACM Trans. Economics and Comput.
·
2021
Full text
Cite
Journal article
SIAM Journal on Computing
·
January 2021
Full text
Cite
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
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
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
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
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
