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

Channel:
Microsoft Research
Subscribers:
342,000
Published on ● Video Link: https://www.youtube.com/watch?v=hHBGKbq79yk


Category:
Vlog
Duration: 49:37
749 views
9

The last decade has seen an increased interest in generalizations of the secretary problem, a classical online selection problem. These generalizations have numerous applications in mechanism design for settings involving the selling of a good (e.g. ads) to agents (e.g. page views) arriving online. The matroid secretary problem is one of the most well-studied variants. It is general enough to deal with complex settings and, at the same time, it is sufficiently restricted to admit strong algorithms. A famous conjecture states that there is in fact a O(1)-competitive algorithm for the matroid secretary problem. This is an online algorithm that, in expectation and up to a constant factor, performs as well as any offline algorithm with perfect information. In this talk, we present a new method that improves on the previously best algorithm, in terms of simplicity and its competitive ratio. The main idea of our algorithm is to decompose the problem into a distribution over a simple type of matroid secretary problems which are easy to solve. We show that this leads to a O(loglog(rank))-competitive procedure. This is joint work with Moran Feldman (EPFL) and Rico Zenklusen (ETHZ).



Other Videos By Microsoft Research


2016-06-21Deep clustering: discriminative embeddings for source separation
2016-06-21Social Computing Symposium 2015: Muse: The Brain Sensing Headband
2016-06-21Advances in Quantum Algorithms and Devices: Welcome and Distributed Denstity Matrices
2016-06-21Circle Packing and Its Applications
2016-06-21Advances in Quantum Algorithms & Devices: Quantum Monte Carlo versus Quantum Adiabatic Optimization
2016-06-21Fast Algorithms for Online Stochastic Convex Programming
2016-06-21Research on Concert Hall Acoustics at Aalto University
2016-06-21Fixed-Energy Harmonic Functions
2016-06-21RDFox — A Modern Materialisation-Based RDF System
2016-06-21Competitive erosion is conformally invariant
2016-06-21A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem
2016-06-21Recent Advances in Deep Learning at Microsoft: A Selected Overview
2016-06-21The Interplay of Social Influence and Own Preference in Social Networks
2016-06-21A Fast Distributed Algorithm for α-Fair Packing Problems
2016-06-21Theory Day Session 3
2016-06-21Provable Submodular Minimization via Wolfe’s Algorithm
2016-06-21A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
2016-06-21Stochastic Methods for Complex Performance Measures: A Tale of Two Families
2016-06-21Parallel Bayesian Network Structure Learning for Genome-Scale Gene Networks
2016-06-21Empirical Inference for Intelligent Systems
2016-06-21Ordered Stick-breaking Prior for Sequential MCMC Inference of Bayesian Non-Parametric Models


Tags:
microsoft research
algorithms