Personne

Ola Nils Anders Svensson

Publications associées (52)

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