  In modern sample-driven Prophet Inequality, an adversary chooses a sequence
of $n$ items with values $v_1, v_2, \ldots, v_n$ to be presented to a decision
maker (DM). The process follows in two phases. In the first phase (sampling
phase), some items, possibly selected at random, are revealed to the DM, but
she can never accept them. In the second phase, the DM is presented with the
other items in a random order and online fashion. For each item, she must make
an irrevocable decision to either accept the item and stop the process or
reject the item forever and proceed to the next item. The goal of the DM is to
maximize the expected value as compared to a Prophet (or offline algorithm)
that has access to all information. In this setting, the sampling phase has no
cost and is not part of the optimization process. However, in many scenarios,
the samples are obtained as part of the decision-making process.
  We model this aspect as a two-phase Prophet Inequality where an adversary
chooses a sequence of $2n$ items with values $v_1, v_2, \ldots, v_{2n}$ and the
items are randomly ordered. Finally, there are two phases of the Prophet
Inequality problem with the first $n$-items and the rest of the items,
respectively. We show that some basic algorithms achieve a ratio of at most
$0.450$. We present an algorithm that achieves a ratio of at least $0.495$.
Finally, we show that for every algorithm the ratio it can achieve is at most
$0.502$. Hence our algorithm is near-optimal.

Optimization and Control;Data Structures and Algorithms