Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information

Richard Santiago, Ivan Sergeev, Rico Zenklusen

Random order online contention resolution schemes (ROCRS) are structured online rounding algorithms with numerous applications and links to other well-known online selection proble…