Research map / Learning theory and algorithms / Combinatorial and search optimization
DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DiMa, a DDPM pre-trained on known hard OBM instances and fine-tuned with a shortcut policy gradient (SPG) RL method to generate harder instances, improving competitive-ratio upper bounds for online matching with random arrivals and stochastic rewards.
Problem
Finding harder input instances to tighten theoretical competitive-ratio upper bounds (hardness) for online bipartite matching variants, where worst-case instances are hand-designed by theoretical computer scientists.
Approach
Model the reverse denoising process of a DiT-based DDPM as an MDP, pre-trained on a distribution of known hard instances (thick-z graphs), and fine-tune it with shortcut policy gradient, which skips denoising steps when computing the policy gradient to converge faster than DDPO.
Key results
- Reproduces the known 1-1/e hardness upper-triangular instance for fractional OBM with Water-filling after SPG fine-tuning.
- Improves the best-known upper bound for Ranking in online matching with random arrivals from 0.727 to 0.723.
- Improves the best-known upper bound for online matching with stochastic rewards from 0.597 to 0.594 (N=10); SPG shows increasing reward while DDPO fails to converge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DiMa to generate a hard instance for Ranking | Ranking on OMRA · OMRA | competitive ratio upper bound: 0.727 -> 0.723 | Helped |
| Use DiMa to generate a hard instance for Balance | Balance on OMSR · OMSR | competitive ratio upper bound: 0.597 -> 0.594 | Helped |
| Fine-tune the pre-trained DDPM with SPG instead of DDPO | DiMa on fractional OBM · Fractional OBM | average reward | Helped |
| Fine-tune with SPG to move from the thick-z distribution toward the upper-triangular distribution | DiMa on fractional OBM · Fractional OBM | competitive ratio | Helped |
Surprising findings
- DDPO with the standard REINFORCE gradient suffers poor convergence and fails to produce any novel harder instances in this setting.
Limitations
- Choice of the perturbation hyperparameter gamma for the initial distribution is crucial; too large or too small fails to find harder instances.
- Theoretical proofs are given only for N=10 instances for the stochastic-rewards case, with larger instances used by the method but not proved.
- Applied only to small instances (|L|=|R| = 20, 40 in fractional OBM experiments) and to a limited set of OBM variants.
Experimental setup
Datasets: thick-z graph distribution (synthetic, 200 graphs)
Benchmarks: fractional online bipartite matching (Water-filling) online matching with random arrivals (Ranking) online matching with stochastic rewards (Balance)
Metrics: competitive ratio average reward
Baselines: DDPO Water-filling Ranking Balance Zhang et al. (2024a) adversarial RL instances
Builds on: DDPM DDIM DDPO REINFORCE Diffusion Transformer (DiT)
Closest papers by meaning
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.90)
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.87)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.86)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.86)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.85)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.