Online Combinatorial Optimization with Graphical Dependencies

Most existing work in online stochastic combinatorial optimization assumes that inputs are drawn from independent distributions—a strong assumption that often fails in practice. At the other extreme, arbitrary correlations are equivalent to worst-case inputs via Yao’s minimax principle, making good algorithms often impossible. This motivates the study of intermediate models that capture mild correlations while still permitting nontrivial algorithms.