18 citations · 45 across the 16 of their papers we have counts for
4 papers · 1 filter
Approximate Fully Dynamic Directed Densest Subgraph
Richard Li, Kent Quanrud
We give a fully dynamic algorithm maintaining a -approximate directed densest subgraph in amortized time or $\tilde{O}(\log^4(…
Independent Sets in Elimination Graphs with a Submodular Objective
Chandra Chekuri, Kent Quanrud
Maximum weight independent set (MWIS) admits a -approximation in inductively -independent graphs and a -approximation in -perfectly orientable graphs.…
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Q…
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…