Dimitris Fotakis

A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities

We study prophet inequalities under intersections of $q$ partition matroids, where an online algorithm irrevocably selects elements with independent nonnegative values drawn from known distributions and revealed in an adversarial order. We prove an $\Omega(q/\log q)$ lower bound on the competitive ratio. Together with...