# Online Combinatorial Optimization with Graphical Dependencies

arXiv: https://arxiv.org/abs/2507.16031 · HTML: https://mlsanity.com/paper/2507.16031/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Adversarial Online Classification with a Preview](https://mlsanity.com/paper/2608.29503/) (2026)

## Abstract (arXiv)

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 Delta, smoothly interpolating between independence (Delta = 0) and full correlation (Delta → ∞). While na"ively this yields eO(Delta)-competitive algorithms and Omega(Delta) hardness, we ask: when can we design tight Theta(Delta)-competitive algorithms? We present general techniques achieving O(Delta)-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.