Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality

Article Computer Science, Software Engineering

Prophet secretary through blind strategies

Jose Correa et al.

Summary: The paper introduces blind strategies that can achieve a better constant for the prophet secretary problem than previous research, and analyzes the limits of the optimal algorithms for the gambler.

MATHEMATICAL PROGRAMMING (2021)

Add to Collection

Article Operations Research & Management Science

Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution

Jose Correa et al.

Summary: The article focuses on the single-choice prophet inequality problem for independent and identically distributed random variables in optimal stopping theory, and discusses the boundaries of the problem. The authors found that in the case where F is unknown, a tight bound of 0.368 is established, related to the optimal solution of the secretary problem. Furthermore, combining the stopping time with a limited number of samples from F significantly improves the solution.

MATHEMATICS OF OPERATIONS RESEARCH (2021)

Add to Collection

Article Operations Research & Management Science

Strong Algorithms for the Ordinal Matroid Secretary Problem

Jose A. Soto et al.

Summary: The study introduces a technique based on forbidden sets to design algorithms with strong probability-competitive ratios on various matroid classes, improving guarantees for almost all matroid classes. Additionally, competitive ratios are achieved in graphic matroids and laminar matroids.

MATHEMATICS OF OPERATIONS RESEARCH (2021)

Add to Collection

Article Computer Science, Hardware & Architecture