Oblivious Algorithms for the Maximum Directed Cut Problem

Uriel Feige, Shlomo Jozeph

This paper introduces a special family of randomized algorithms for Max DICUT that we call oblivious algorithms. Let the bias of a vertex be the ratio between the total weight of i…