Beyond matroids: Secretary Problem and Prophet Inequality with general constraints

Fuente: arXiv
Enregistré dans:
Détails bibliographiques
Auteur principal: Rubinstein, Aviad
Format: Preprint
Publié: 2016
Sujets:
Accès en ligne:
Tags: Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
_version_ 1866917767482966016
author Rubinstein, Aviad
author_facet Rubinstein, Aviad
contents We study generalizations of the "Prophet Inequality" and "Secretary Problem", where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we give O(log n)-competitive algorithms for both problems. This is close to the Ω(log n / loglog n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log n log r)-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(log r loglog n) factors) an open question posed to us by Bobby Kleinberg.
format Preprint
id arxiv_https___arxiv_org_abs_1604_00357
institution arXiv
publishDate 2016
record_format arxiv
spellingShingle Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
Rubinstein, Aviad
Data Structures and Algorithms
Computer Science and Game Theory
We study generalizations of the "Prophet Inequality" and "Secretary Problem", where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we give O(log n)-competitive algorithms for both problems. This is close to the Ω(log n / loglog n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log n log r)-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(log r loglog n) factors) an open question posed to us by Bobby Kleinberg.
title Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
topic Data Structures and Algorithms
Computer Science and Game Theory
url https://arxiv.org/abs/1604.00357