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.

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 ∆, smoothly interpolating between independence (∆ = 0) and full correlation (∆ → ∞). While naïvely this yields e O(∆) -competitive algorithms and Ω(∆) hardness, we ask: when can we design tight Θ(∆)-competitive algorithms?

We present general techniques achieving O(∆)-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 [KPS + 19, LMV + 21, CCF + 21]. For maximization problems (e.g., matchings and combinatorial auctions with XOS buyers), we extend the "balanced prices" framework for online allocation problems [DFKL20] to MRFs.