smoothed online combinatorial optimization considers a learner who repeatedly
chooses a combinatorial decision to minimize an unknown changing cost function
with a penalty on switching decisions in consecutive rounds. We study smoothed
online combinatorial optimization problems when an