Before revision:  We additionally show }  it is possible to asymptotically achieve an exact \beta approximation ratio for several natural classes of problem instances, including small prophets (where each distribution is concentrated near zero) and frequent prophets (where each distribution occurs at least some number of times) .
After revision:  We additionally show } it is possible to achieve the optimal approximation ratio of \beta (improving over the previous best-known bound of 0.738). - We give a new, simpler proof of Kertz's optimal approximation guarantee of \beta \approx 0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. - Using this decomposition in combination with a novel convex programming formulation, we construct the first Efficient PTAS for the Optimal Ordering problem .