Online Combinatorial Optimization with Graphical Dependencies
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908639810289664 |
|---|---|
| author | Gao, Zhimeng Gergatsouli, Evangelia Patton, Kalen Singla, Sahil |
| author_facet | Gao, Zhimeng Gergatsouli, Evangelia Patton, Kalen Singla, Sahil |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16031 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Combinatorial Optimization with Graphical Dependencies Gao, Zhimeng Gergatsouli, Evangelia Patton, Kalen Singla, Sahil Data Structures and Algorithms F.2.2 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. |
| title | Online Combinatorial Optimization with Graphical Dependencies |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2507.16031 |