Lune

STOC2026Top-tier venue

Online Combinatorial Optimization with Graphical Dependencies

Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, Sahil Singla

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 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Learning from a Sample in Online Algorithms cites Robust Online Correlation Clustering
  • Learning from a Sample in Online Algorithms cites Competitive Analysis with a Sample and the Secretary Problem
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on10

  1. Competitive Analysis with a Sample and the Secretary ProblemHaim Kaplan, David Naori, Danny RazSODA 2020 · 26 citations
  2. Robust Online Correlation ClusteringSilvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang et al.NeurIPS 2021 · 25 citations
  3. A Constant Factor Prophet Inequality for Online Combinatorial AuctionsJosé Correa, Andrés CristiSTOC 2023 · 18 citations
  4. The Two-Sided Game of Googol and Sample-Based Prophet InequalitiesJosé R. Correa, Andrés Cristi, Boris Epstein, José A. SotoSODA 2020 · 16 citations
  5. Learning from a Sample in Online AlgorithmsC. J. Argue, Alan M. Frieze, Anupam Gupta, Christopher SeilerNeurIPS 2022 · 16 citations

Related papers

  1. (Fractional) online stochastic matching via fine-grained offline statisticsZhihao Gavin Tang, Jinzhao Wu, Hongxun WuSTOC 2022 · 9 citations
  2. Stronger adversaries grow cheaper forests: online node-weighted Steiner problemsSander Borst, Marek Eliás, Moritz VenzinSODA 2025 · 1 citation
  3. Approximation Algorithms for Stochastic Minimum-Norm Combinatorial OptimizationSharat Ibrahimpur, Chaitanya SwamyFOCS 2020 · 8 citations
  4. Simple and Optimal Greedy Online Contention Resolution SchemesVasilis LivanosNeurIPS 2022 · 1 citation
  5. Online edge coloring via tree recurrences and correlation decayJanardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney et al.STOC 2022 · 7 citations
Dusk over the sea between two cliffs drawn in fine vertical lines