Jakub Kozik - Dynamic Threshold Strategy for Universal Best Choice Problem

dmtcs:2767 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2767
Dynamic Threshold Strategy for Universal Best Choice ProblemArticle

Authors: Jakub Kozik 1

  • 1 Theoretical Computer Science Department [Krakow]

We propose a new strategy for universal best choice problem for partially ordered sets. We present its partial analysis which is sufficient to prove that the probability of success with this strategy is asymptotically strictly greater than 1/4, which is the value of the best universal strategy known so far.

https://doi.org/10.46298/dmtcs.2767
Source: HAL:hal-01185565v1
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: partial order,secretary problem,best choice,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

5 Documents citing this article

Share and export

Consultation statistics

This page has been seen 261 times.
This article's PDF has been downloaded 366 times.