16 citations · 46 across the 15 of their papers we have counts for
23 papers
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
Xinrui Jia, Ola Svensson, Weiqiang Yuan
Given a graph with edges colored red or blue and an integer , the exact perfect matching problem asks if there exists a perfect matching with exactly red edges. There exists…
Submodular Maximization Subject to Matroid Intersection on the Fly
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson +1
Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especial…
Flow Time Scheduling and Prefix Beck-Fiala
Nikhil Bansal, Lars Rohwedder, Ola Svensson
We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction t…
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…
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…