Ola Nils Anders Svensson

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ola Nils Anders Svensson

Chat with Graph Search

The Cost of Consistency: Submodular Maximization with Constant Recourse

Centrality of trees for capacitated -center

Semi-streaming algorithms for submodular matroid intersection

The Price of Explainability for Clustering

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

A Framework for the Secretary Problem on the Intersection of Matroids

LP-Based Algorithms for Capacitated Facility Location

Fair Colorful k-Center Clustering

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

A FRAMEWORK FOR THE SECRETARY PROBLEM ON THE INTERSECTION OF MATROIDS

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

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

Hardness Of Precedence Constrained Scheduling On Identical Machines

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

Deterministic Online Bipartite Edge Coloring

Online Edge Coloring Is (Nearly) as Easy as Offline

Streaming Submodular Maximization Under Matroid Constraints

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

Constant factor approximation for ATSP with two edge weights