Publications by Rico Zenklusen

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

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

Rico Zenklusen, Ola Nils Anders Svensson, Ashkan Norouzi Fard, Moran Feldman

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

An Improved Analysis of Local Search for Max-Sum Diversification

Rico Zenklusen, Friedrich Eisenbrand, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

A Framework for the Secretary Problem on the Intersection of Matroids

Rico Zenklusen, 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

A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

Rico Zenklusen, Ola Nils Anders Svensson, Moran Feldman

2018

Stable Routing And Unique-Max Coloring On Trees

Rico Zenklusen, Nicolai Hähnle, Laura Sanità

Some of the routing protocols used in telecommunication networks route traffic on a shortest path tree according to configurable integral link weights. One crucial issue for network operators is finding a weight function that ensures a stable routing: when ...

SIAM Publications2013

A note on chromatic properties of threshold graphs

Dominique de Werra, Bernard Ries, Rico Zenklusen

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a simila ...

Elsevier2012

Blockers and transversals

Dominique de Werra, Bernard Ries, Rico Zenklusen

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

Elsevier2009