research
∙
07/05/2023
Independent Sets in Elimination Graphs with a Submodular Objective
Maximum weight independent set (MWIS) admits a 1/k-approximation in indu...
share
research
∙
05/04/2023
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
Boob et al. [1] described an iterative peeling algorithm called Greedy++...
research
∙
03/02/2023
Faster exact and approximation algorithms for packing and covering matroids via push-relabel
Matroids are a fundamental object of study in combinatorial optimization...
research
∙
10/06/2022
(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time
We consider the problem of maintaining a (1-ϵ)-approximation to the dens...
research
∙
11/17/2021
Minimum Cuts in Directed Graphs via Partial Sparsification
We give an algorithm to find a minimum cut in an edge-weighted directed ...
research
∙
04/15/2021
Faster Algorithms for Rooted Connectivity in Directed Graphs
We consider the fundamental problems of determining the rooted and globa...
research
∙
04/14/2021
Fast Approximations for Rooted Connectivity in Weighted Directed Graphs
We consider approximations for computing minimum weighted cuts in direct...
research
∙
03/24/2021
Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems
Li and Panigrahi, in recent work, obtained the first deterministic algor...
research
∙
03/08/2021
Online Directed Spanners and Steiner Forests
We present online algorithms for directed spanners and Steiner forests. ...
research
∙
11/06/2020
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
We develop fast near-linear time approximation algorithms for the minimu...
research
∙
11/01/2019
Computing Circle Packing Representations of Planar Graphs
The Circle Packing Theorem states that every planar graph can be represe...
research
∙
07/09/2019
On Approximating Partial Set Cover and Generalizations
Partial Set Cover (PSC) is a generalization of the well-studied Set Cove...
research
∙
02/22/2019
ℓ_1-sparsity Approximation Bounds for Packing Integer Programs
We consider approximation algorithms for packing integer programs (PIPs)...
research
∙
11/30/2018
Parallelizing greedy for submodular set function maximization in matroids and beyond
We consider parallel, or low adaptivity, algorithms for submodular funct...
research
∙
10/14/2018
Approximating optimal transport with linear programs
In the regime of bounded transportation costs, additive approximations f...
research
∙
08/17/2018
LP Relaxation and Tree Packing for Minimum k-cuts
Karger used spanning tree packings to derive a near linear-time randomiz...
research
∙
07/30/2018
On Approximating (Sparse) Covering Integer Programs
We consider approximation algorithms for covering integer programs of th...
research
∙
07/23/2018
Submodular Function Maximization in Parallel via the Multilinear Relaxation
Balkanski and Singer [5] recently initiated the study of adaptivity (or ...
research
∙
07/18/2018
Fast and Deterministic Approximations for k-Cut
In an undirected graph, a k-cut is a set of edges whose removal breaks t...
research
∙
02/05/2018
Fast Approximations for Metric-TSP via Linear Programming
We develop faster approximation algorithms for Metric-TSP building on re...
research
∙
05/20/2016
