Purchasing a C_4 online

Michael Anastos

Let $G$ be a graph with edge set $(e_1,e_2,...e_N)$. We independently associate to each edge $e_i$ of $G$ a cost $x_i$ that is drawn from a Uniform [0, 1] distribution. Suppose $…