Ola Nils Anders Svensson

About
Privacy
Disclaimer

Graph Chatbot

Related publications (51)

Page 3 of 3

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

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

Constant factor approximation for ATSP with two edge weights

Ola Nils Anders Svensson, Jakub Tarnawski

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 case of unit edge weights, the first constant factor approximation was give ...

SPRINGER HEIDELBERG2018

On the configuration LP for maximum budgeted allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Aleksander Madry

We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer Heidelberg2015

Online Matching with General Arrivals

Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

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 vertices arriving only on one side, and presented optimal deterministic and randomi ...

IEEE COMPUTER SOC2019

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

Ola Nils Anders Svensson, Moran Feldman, Ashkan Norouzi Fard

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 multi-player model t ...

ASSOC COMPUTING MACHINERY2020

Approximating ATSP by Relaxing Connectivity

Ola Nils Anders Svensson

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments a ...

2015

On the Approximability of Single-Machine Scheduling with Precedence Constraints

Ola Nils Anders Svensson

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cove ...

2011

Constant Factor Approximation for ATSP with Two Edge Weights

Ola Nils Anders Svensson, Jakub Tarnawski

Springer Int Publishing Ag2016

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

Weighted Matchings via Unweighted Augmentations

Sagar Sudhir Kale, Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

ASSOC COMPUTING MACHINERY2019