research
∙
07/06/2023
Efficient parallel implementation of the multiplicative weight update method for graph-based linear programs
Positive linear programs (LPs) model many graph and operations research ...
share
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...
research
∙
06/03/2023
On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms
Dense subgraph discovery is an important problem in graph mining and net...
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/22/2023
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
We consider the feedback vertex set problem in undirected graphs (FVS). ...
research
∙
11/15/2022
Approximating Flexible Graph Connectivity via Räcke Tree based Rounding
Flexible graph connectivity is a new network design model introduced by ...
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
∙
10/04/2022
Bicriteria Approximation Algorithms for Priority Matroid Median
Fairness considerations have motivated new clustering problems and algor...
research
∙
09/25/2022
Augmentation based Approximation Algorithms for Flexible Network Design
Adjiashvili introduced network design in a non-uniform fault model: the ...
research
∙
07/08/2021
On Submodular Prophet Inequalities and Correlation Gap
Prophet inequalities and secretary problems have been extensively studie...
research
∙
04/15/2021
Faster Algorithms for Rooted Connectivity in Directed Graphs
We consider the fundamental problems of determining the rooted and globa...
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/04/2021
Revisiting Priority k-Center: Fairness and Outliers
In the Priority k-Center problem, the input consists of a metric space (...
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
∙
09/25/2020
Hypergraph k-cut for fixed k in deterministic polynomial time
We consider the Hypergraph-k-cut problem. The input consists of a hyperg...
research
∙
11/04/2019
Algorithms for Intersection Graphs of Multiple Intervals and Pseudo Disks
Intersection graphs of planar geometric objects such as intervals, disks...
research
∙
10/16/2019
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
We consider node-weighted survivable network design (SNDP) in planar gra...
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
∙
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
∙
06/11/2018
Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations
We consider clustering in the perturbation resilience model that has bee...
research
∙
02/05/2018
