Publications related to Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

An Improved Analysis of Local Search for Max-Sum Diversification

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

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

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

Deterministic Algorithms for Submodular Maximization Problems

Moran Feldman

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...

ASSOC COMPUTING MACHINERY2018

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Algorithms For Clustering Problems

Ashkan Norouzi Fard

Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...

EPFL2018

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Nisheeth Vishnoi, Javad Ebrahimi Boroojeni, Damian Mateusz Straszak

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...

Ieee2017

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by c ...

Association for Computing Machinery2017

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Information Structure Design in Team Decision Problems

Maryam Kamgarpour, Tyler Summers

We consider a problem of information structure design in team decision problems and team games. We propose simple, scalable greedy algorithms for adding a set of extra information links to optimize team performance and resilience to non-cooperative and adv ...

2017

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Graph Chatbot

Chat with Graph Search

An Improved Analysis of Local Search for Max-Sum Diversification

A Framework for the Secretary Problem on the Intersection of Matroids

Deterministic Algorithms for Submodular Maximization Problems

Robust Maximization of Non-Submodular Objectives

Algorithms For Clustering Problems

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Maximizing Symmetric Submodular Functions

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Information Structure Design in Team Decision Problems

An Improved Analysis of Local Search for Max-Sum Diversification

Deterministic Algorithms for Submodular Maximization Problems

Algorithms For Clustering Problems

Robust Maximization of Non-Submodular Objectives

A Framework for the Secretary Problem on the Intersection of Matroids

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Maximizing Symmetric Submodular Functions

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Information Structure Design in Team Decision Problems