42 citations · 204 across the 38 of their papers we have counts for
45 papers
The Price of Explainability for Clustering
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson +1
Given a set of points in -dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 20…
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…
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
Etienne Bamas, Marina Drygala, Ola Svensson
The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap -edge connecte…
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…
Fast and Accurate -means++ via Rejection Sampling
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard +2
-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide a…
Consistent k-Clustering for General Metrics
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard +1
Given a stream of points in a metric space, is it possible to maintain a constant approximate clustering by changing the cluster centers only a small number of times during the ent…
The Primal-Dual method for Learning Augmented Algorithms
Étienne Bamas, Andreas Maggiori, Ola Svensson
The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms…
Learning Augmented Energy Minimization via Speed Scaling
Étienne Bamas, Andreas Maggiori, Lars Rohwedder +1
As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a…
Fair Colorful k-Center Clustering
Xinrui Jia, Kshiteej Sheth, Ola Svensson
An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is t…
Robust Algorithms under Adversarial Injections
Paritosh Garg, Sagar Kale, Lars Rohwedder +1
In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the wo…
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson +1
We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studi…
Beating Greedy for Stochastic Bipartite Matching
Buddhima Gamlath, Sagar Kale, Ola Svensson
We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independent…
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Nikhil Bansal, Ola Svensson, Luca Trevisan
A sparsifier of a graph (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph that approximately retains the cut structure of . For general graphs…
Online Matching with General Arrivals
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori +2
The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertice…
Weighted Matchings via Unweighted Augmentations
Buddhima Gamlath, Sagar Kale, Slobodan Mitrović +1
We design a generic method for reducing the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide eff…
Beyond -Approximation for Submodular Maximization on Massive Data Streams
Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović +3
Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc., require extracting a small but representati…
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Buddhima Gamlath, Sangxia Huang, Ola Svensson
We study -means clustering in a semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we inves…
On bounded pitch inequalities for the min-knapsack polytope
Yuri Faenza, Igor Malinović, Monaldo Mastrolilli +1
In the min-knapsack problem one aims at choosing a set of objects with minimum total cost and total profit above a given threshold. In this paper, we study a class of valid inequal…