Before revision:  We look at several online optimization problems : mincut, maxcut and submodular maximization and show that there are input ordering where a greedy strategy can produce an optimalanswer\mc .
After revision:  We look at several online optimization problems : mincut, maxcut and submodular maximization and show that there are input ordering where a greedy strategy can produce an optimalanswer\mc-type problems with respect to greedy strategies. Finally we consider a non-stationary regret setting with a variational budget V_T and give tights bounds on the regret function. Specifically, we show that if V_T is sublinear in T (number of rounds) then there is a deterministic algorithm achieving a sublinear regret bound (O(V_T)). Further, this is optimal, even if randomization is allowed .