16 citations · 61 across the 32 of their papers we have counts for
8 papers · 1 filter
Faster Exact and Approximate Algorithms for -Cut
Anupam Gupta, Euiwoong Lee, Jason Li
In the -cut problem, we are given an edge-weighted graph and an integer , and have to remove a set of edges with minimum total weight so that has at least connect…
Non-Preemptive Flow-Time Minimization via Rejections
Anupam Gupta, Amit Kumar, Jason Li
We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results…
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
Mohsen Ghaffari, Jason Li
We show that many classical optimization problems --- such as -approximate maximum flow, shortest path, and transshipment --- can be computed in $\newcommand{\tmix}{τ_{\te…
Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
Benjamin Jauregui, Jason Li, Pedro Montealegre +1
Algorithmic meta-theorems, stating that graph properties expressible in some particular logic can be decided efficiently in graph classes having some specific structural properties…
Distributed Computation in Node-Capacitated Networks
John Augustine, Mohsen Ghaffari, Robert Gmyr +4
In this paper, we study distributed graph algorithms in networks in which the nodes have a limited communication capacity. Many distributed systems are built on top of an underlyin…
Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li +2
We study the problem of deleting the smallest set of vertices (resp. edges) from a given graph such that the induced subgraph (resp. subgraph) belongs to so…