Deterministic decremental sssp and approximate min-cost flow in almost-linear time
A Bernstein, MP Gutenberg… - 2021 IEEE 62nd Annual …, 2022 - ieeexplore.ieee.org
In the decremental single-source shortest paths problem, the goal is to maintain distances
from a fixed source s to every vertex v in an m-edge graph undergoing edge deletions. In …
from a fixed source s to every vertex v in an m-edge graph undergoing edge deletions. In …
Dynamic algorithms for packing-covering lps via multiplicative weight updates
In the dynamic linear program (LP) problem, we are given an LP undergoing updates and
we need to maintain an approximately optimal solution. Recently, significant attention (eg …
we need to maintain an approximately optimal solution. Recently, significant attention (eg …
Submodular function maximization in parallel via the multilinear relaxation
Balkanski and Singer [4] recently initiated the study of adaptivity (or parallelism) for
constrained submodular function maximization, and studied the setting of a cardinality …
constrained submodular function maximization, and studied the setting of a cardinality …
Approximating optimal transport with linear programs
K Quanrud - arXiv preprint arXiv:1810.05957, 2018 - arxiv.org
arXiv:1810.05957v2 [cs.DS] 21 Oct 2018 Page 1 arXiv:1810.05957v2 [cs.DS] 21 Oct 2018
Approximating optimal transport with linear programs Kent Quanrud∗ October 23, 2018 Abstract …
Approximating optimal transport with linear programs Kent Quanrud∗ October 23, 2018 Abstract …
Faster approximation algorithms for geometric set cover
We improve the running times of $ O (1) $-approximation algorithms for the set cover
problem in geometric settings, specifically, covering points by disks in the plane, or covering …
problem in geometric settings, specifically, covering points by disks in the plane, or covering …
Fast LP-based approximations for geometric packing and covering problems
We derive fast approximation schemes for LP relaxations of several well-studied geometric
optimization problems that include packing, covering, and mixed packing and covering …
optimization problems that include packing, covering, and mixed packing and covering …
On approximating (sparse) covering integer programs
We consider approximation algorithms for covering integer programs of the form min〈 c, x〉
over x∊ ℤ≥ 0 n st Ax≥ b and x≤ d; where A∊ ℝ≥ 0 m× n, b∊ ℝ≥ 0 m, and c, d∊ ℝ≥ 0 n …
over x∊ ℤ≥ 0 n st Ax≥ b and x≤ d; where A∊ ℝ≥ 0 m× n, b∊ ℝ≥ 0 m, and c, d∊ ℝ≥ 0 n …
Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
X Mao - Proceedings of the 56th Annual ACM Symposium on …, 2024 - dl.acm.org
The All-Pairs Shortest Paths (APSP) problem is one of the fundamental problems in
theoretical computer science. It asks to compute the distance matrix of a given n-vertex …
theoretical computer science. It asks to compute the distance matrix of a given n-vertex …
Partial resampling to approximate covering integer programs
We consider positive covering integer programs, which generalize set cover and which have
attracted a long line of research developing (randomized) approximation algorithms …
attracted a long line of research developing (randomized) approximation algorithms …
Multiplicative auction algorithm for approximate maximum weight bipartite matching
DW Zheng, M Henzinger - Mathematical Programming, 2024 - Springer
We present an auction algorithm using multiplicative instead of constant weight updates to
compute a (1-ε)-approximate maximum weight matching (MWM) in a bipartite graph with n …
compute a (1-ε)-approximate maximum weight matching (MWM) in a bipartite graph with n …