Publications by Ola Nils Anders Svensson

Deterministic Online Bipartite Edge Coloring

We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is (2 — o (1))-competitive, which is optimal for graphs of low maximum degree, Δ = O (log n) [BNMN IPL’92]. Numerous online edg ...

Society for Industrial and Applied Mathematics2025

The Cost of Consistency: Submodular Maximization with Constant Recourse

Ola Nils Anders Svensson

In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowe ...

ACM2025

Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection

Ola Nils Anders Svensson

For any 𝜀 > 0, we prove that 𝑘-Dimensional Matching is hard to approximate within a factor of 𝑘/(12+𝜀) for large 𝑘 unless NP ⊆ BPP. Listed in Karp’s 21 NP-complete problems, 𝑘-Dimensional Matching is a benchmark computational complexity problem which we fi ...

ACM2025

A (2+ε)-Approximation Algorithm for Metric 𝑘-Median

Ola Nils Anders Svensson

In the classical NP-hard (metric) 𝑘-median problem, we are given a set of 𝑛 clients and centers with metric distances between them, along with an integer parameter 𝑘 ≥ 1. The objective is to select a subset of 𝑘 open centers that minimizes the total distan ...

ACM2025

Streaming Submodular Maximization Under Matroid Constraints

Ola Nils Anders Svensson

Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, includi ...

INFORMS2025

Data-Driven Solution Portfolios

Ola Nils Anders Svensson

In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select k potential solutions, with the goal of optimizing the value of the best solution. More ...

2025

Online Edge Coloring Is (Nearly) as Easy as Offline

Ola Nils Anders Svensson

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree Δcan be edge colored (offline) using no more than Γ+1 colors (with Δbeing a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL'92) conject ...

Association for Computing Machinery2024

The Price of Explainability for Clustering

Ola Nils Anders Svensson

Given a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio be ...

Ieee Computer Soc2023

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Ola Nils Anders Svensson

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 studied in various computational models. We consider a clean multiplayer model th ...

ASSOC COMPUTING MACHINERY2023

A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem

Ola Nils Anders Svensson, Etienne Michel François Bamas

The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap 2-edge connected subgraphs. This has culminated in a 5/3-approximation algorithm. However, th ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Semi-streaming algorithms for submodular matroid intersection

Ola Nils Anders Svensson, Paritosh Garg

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

Igor Malinovic, Ola Nils Anders Svensson

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

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 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

Rico Zenklusen, Ola Nils Anders Svensson, Moran Feldman

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