42 citations · 204 across the 38 of their papers we have counts for
5 papers · 1 filter
Towards Non-Uniform k-Center with Constant Types of Radii
Xinrui Jia, Lars Rohwedder, Kshiteej Sheth +1
In the Non-Uniform k-Center problem we need to cover a finite metric space using k balls of different radii that can be scaled uniformly. The goal is to minimize the scaling factor…
A QPTAS for stabbing rectangles
Friedrich Eisenbrand, Martina Gallato, Ola Svensson +1
We consider the following geometric optimization problem: Given axis-aligned rectangles in the plane, the goal is to find a set of horizontal segments of minimum total length…
Streaming Submodular Maximization under Matroid Constraints
Moran Feldman, Paul Liu, Ashkan Norouzi-Fard +2
Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniqu…
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
Buddhima Gamlath, Xinrui Jia, Adam Polak +1
We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A -clustering is said to be explainabl…
Semi-Streaming Algorithms for Submodular Matroid Intersection
Paritosh Garg, Linus Jordan, Ola Svensson
While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of for the \emph{unweighted} matching problem, it was only recently that Paz a…