Ola Nils Anders Svensson

Related publications (52)

About
Privacy
Disclaimer

Graph Chatbot

Semi-streaming algorithms for submodular matroid intersection

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is ...

SPRINGER HEIDELBERG2022

Flow Time Scheduling and Prefix Beck-Fiala

Ola Nils Anders Svensson, Lars Rohwedder

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 that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bound ...

ASSOC COMPUTING MACHINERY2022

On inequalities with bounded coefficients and pitch for the min knapsack polytope

Ola Nils Anders Svensson, Igor Malinovic

The min knapsack problem appears as a major component in the structure of capacitated covering problems. Its polyhedral relaxations have been extensively studied, leading to strong relaxations for networking, scheduling and facility location problems. ...

ELSEVIER2022

Fair colorful k-center clustering

Ola Nils Anders Svensson, Xinrui Jia

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 to find the smallest radius rho such that there exist balls of radius rho aro ...

SPRINGER HEIDELBERG2022

A FRAMEWORK FOR THE SECRETARY PROBLEM ON THE INTERSECTION OF MATROIDS

Ola Nils Anders Svensson

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 subset of elements subject to given constraints, where elements arrive one- ...

Siam Publications2022

Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

Ola Nils Anders 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 (3/2-c)-approximation algorithm for some fixed c > 0, improving upon the long-standing bound of 3/2. To do this, w ...

2021

Semi-streaming Algorithms for Submodular Matroid Intersection

Ola Nils Anders Svensson, Paritosh Garg

SPRINGER INTERNATIONAL PUBLISHING AG2021

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Ola Nils Anders Svensson, Adam Teodor Polak, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Xinrui Jia

We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A k-clustering is said to be explainable if it is given by a decision tree where each internal node splits data point ...

2021

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Justin Dean Ward

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local ...

SIAM PUBLICATIONS2020

Page 2 of 6