Publication

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Publications associées (32)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

A New Framework for Distributed Submodular Maximization

Justin Dean Ward

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

Ieee2016

Maximizing k-Submodular Functions and Beyond

Justin Dean Ward

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

Assoc Computing Machinery2016

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Ya-Ping Hsieh, Ashkan Norouzi Fard, Abbas Bazzi, Marwa El Halabi

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

2016

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

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

EPFL2016

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

Moran Feldman

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

Siam Publications2015

Constrained Binary Identification Problem

Amin Karbasi, Morteza Zadimoghaddam

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...

2013

Testing Alternative Ground Water Models Using Cross-Validation and Other Methods

Paolo Perona

Many methods can be used to test alternative ground water models. Of concern in this work are methods able to (1) rank alternative models (also called model discrimination) and (2) identify observations important to parameter estimates and predictions (equ ...

Wiley-Blackwell2007

Tree-Based Pursuit: Algorithm and Properties

Pascal Frossard, Pierre Vandergheynst, Philippe Jost

This paper proposes a tree-based pursuit algorithm that efficiently trades off complexity and approximation performance for overcomplete signal expansions. Finding the sparsest representation of a signal using a redundant dictionary is, in general, a NP-Ha ...

2006

Tree-Based Pursuit: Algorithm and Properties

Pascal Frossard, Pierre Vandergheynst, Philippe Jost

2005

Fast Sparse Gaussian Process Methods: The Informative Vector Machine

Matthias Seeger

We present a framework for sparse Gaussian process (GP) methods which uses forward selection with criteria based on information-theoretic principles, previously suggested for active learning. Our goal is not only to learn d-sparse predictors (which can be ...

2003