Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems: Free-Order Prophets Admits an EPTAS, a t(ε)·poly(n)-Time (1 − ε)-Approximate OrderResearch Paper
In Free-Order Prophets a decision maker faces independent non-negative random values with known laws, chooses in advance the order in which to inspect them, and on seeing each value must stop and take it or move on for good. The problem models selection with a sequence the decision maker controls: sequencing interviews, or inspecting alternatives whose…