Recherche

Afficher tous les résultats pour

Accueil

Personne

Ola Nils Anders Svensson

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (51)

Page 2 sur 3

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

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

Centrality of trees for capacitated -center

Ola Nils Anders Svensson

We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...

Springer Heidelberg2015

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

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

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...

UNIV CHICAGO, DEPT COMPUTER SCIENCE2018

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

Ola Nils Anders Svensson

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + root 3 + epsilon, improving upon the decade-old ratio of 3 + epsilon. Our improved approximation ratio is achieved by exploiting the power of pseudo-app ...

Siam Publications2016

Data-Driven Solution Portfolios

Miltiadis Stouras, Ola Nils Anders Svensson, Marina Rebekah Rosie Drygala

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

A Framework for the Secretary Problem on the Intersection of Matroids

Ola Nils Anders Svensson, Moran Feldman

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

ASSOC COMPUTING MACHINERY2018

On Bounded Pitch Inequalities for the Min-Knapsack Polytope, Combinatorial Optimization

Ola Nils Anders Svensson, Yuri Faenza, Igor Malinovic

2018

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...

IEEE2014

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 ρ such that there exist balls of radius ρ around ...

Springer2020

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Chidambaram Annamalai

We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a ce ...

2015

A FRAMEWORK FOR THE SECRETARY PROBLEM ON THE INTERSECTION OF MATROIDS

Ola Nils Anders Svensson

Siam Publications2022

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

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

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

Hardness Of Precedence Constrained Scheduling On Identical Machines

Ola Nils Anders Svensson

In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best algori ...

2011

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

Ola Nils Anders Svensson, Théophile François Thiery

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

Deterministic Online Bipartite Edge Coloring

Ola Nils Anders Svensson, Radu Vintan

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

Online Edge Coloring Is (Nearly) as Easy as Offline

Ola Nils Anders Svensson, Radu Vintan

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