Online Combinatorial Optimization with Graphical Dependencies

Abstract

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 non-trivial algorithms. In this paper, we study online combinatorial optimization under Markov Random Fields (MRFs), a well-established graphical model for structured dependencies. MRFs parameterize correlation strength via the maximum weighted degree $\hat{I}”$, smoothly interpolating between independence ($\hat{I}”=0$) and full correlation ($\hat{I}”\to \infty$). While naïvely this yields $e^{O(\hat{I}”)}$-competitive algorithms and $\hat{I}\text{c◯}(\hat{I}”)$ hardness, we ask: when can we design tight $\hat{I}˜(\hat{I}”)$-competitive algorithms? We present general techniques achieving $O(\hat{I}”)$-competitive algorithms for both minimization and maximization problems under MRF-distributed inputs. For minimization problems with coverage constraints (e.g., Facility Location and Steiner Tree), we reduce to the well-studied $p$-sample model. For maximization problems (e.g., matchings and combinatorial auctions with XOS buyers), we extend the "balanced prices" framework for online allocation problems to MRFs.