{"ID":2892445,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.16031","arxiv_id":"2507.16031","title":"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 $Δ$, smoothly interpolating between independence ($Δ= 0$) and full correlation ($Δ\\to \\infty$). 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. For maximization problems (e.g., matchings and combinatorial auctions with XOS buyers), we extend the \"balanced prices\" framework for online allocation problems to MRFs.","short_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...","url_abs":"https://arxiv.org/abs/2507.16031","url_pdf":"https://arxiv.org/pdf/2507.16031v2","authors":"[\"Zhimeng Gao\",\"Evangelia Gergatsouli\",\"Kalen Patton\",\"Sahil Singla\"]","published":"2025-07-21T19:51:54Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}