42 citations · 204 across the 38 of their papers we have counts for
35 papers · 1 filter
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…
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…
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…
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…
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…
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…
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, László A. Végh
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP rela…
A Framework for the Secretary Problem on the Intersection of Matroids
Moran Feldman, Ola Svensson, Rico Zenklusen
The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight…
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson +1
Clustering is a classic topic in optimization with -means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algori…
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
Christos Kalaitzis, Ola Svensson, Jakub Tarnawski
We consider the classic problem of scheduling jobs on unrelated machines so as to minimize the weighted sum of completion times. Recently, for a small constant , B…
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, Ola Svensson
We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a -approximation algorithm for…
Constant Factor Approximation for ATSP with Two Edge Weights
Ola Svensson, Jakub Tarnawski, László A. Végh
We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the…