Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

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 thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

We provide a counterexample to the performance guarantee obtained in the paper "Il'ev, V., Linker, N., 2006. Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the Eur ...

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

The central task in many interactive machine learning systems can be formalized as the sequential optimization of a black-box function. Bayesian optimization (BO) is a powerful model-based framework for \emph{adaptive} experimentation, where the primary go ...

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

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

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

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

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

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

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

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

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

Observers discriminated the numerical proportion of two sets of elements (N = 9, 13, 33, and 65) that differed either by color or orientation. According to the standard Thurstonian approach, the accuracy of proportion discrimination is determined by irredu ...

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k >= 2 and 1

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream wi ...

We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2(N) -> R+, and the objective is to find a subset S subset of N maximizing f(S). This is one of the most basic submodular optimization ...

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Chat with Graph Search

Approximation Algorithms for Allocation and Network Design

Streaming and Matching Problems with Submodular Functions

A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

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

Robust Adaptive Decision Making: Bayesian Optimization and Beyond

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 : Theoretical Guarantees and Empirical Evaluations

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

Discrimination of numerical proportions: A comparison of binomial and Gaussian models

A New Framework for Distributed Submodular Maximization

Maximizing k-Submodular Functions and Beyond

Approximation algorithms for geometric dispersion

An Efficient Streaming Algorithm for the Submodular Cover Problem

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization