# Spaeh, Ene, Nguyen 2025 - Online and Streaming Algorithms for Constrained k-Submodular Maximization

## One-paragraph Summary

Day la paper tong hop va day manh dong `online / streaming constrained k-submodular`. No xay mot framework threshold-based cho nhieu setting: monotone va general objectives, cardinality constraints theo tung part, partition-matroid submodular corollaries, va trong appendix con mo rong sang knapsack khi item sizes nho so voi budgets. Dong gop de nho nhat la: monotone cardinality line duoc nang tu moc `1/4` len den xap xi `0.3178` khi budget lon; general cardinality line dat constant factor online/streaming huu ich, voi moc it nhat `1/8` va tien dan den khoang `0.1589`; va paper nay la cau noi giua Ene-Nguyen 2022 va cac ket qua packing / partition-matroid ve sau.

## Classification Rationale

Paper thuoc `k-submodular` vi doi tuong chinh van la ham `k`-submodular duoi constrained allocation. Trong repo nay, no la moc rong hon Ene-Nguyen 2022: thay vi chi monotone per-coordinate cardinality, paper xu ly ca non-monotone va mo rong sang knapsack. Vi vay, no nen duoc xem nhu note framework quan trong trong nhom `k-submodular`.

## Setup

- Domain / model: `k`-submodular function tren `k` part roi nhau, voi budgets `n_a` theo tung part cho cardinality setting.
- Streaming / online model: item den tung cai mot; thuat toan inspection mot lan, phu hop voi online free disposal.
- Main settings:
  - monotone `k`-submodular under individual cardinality constraints
  - general `k`-submodular under individual cardinality constraints
  - monotone / general submodular under partition matroid
  - monotone `k`-submodular under individual knapsack constraints khi max item size nho
  - monotone `k`-submodular under common cardinality constraint

## Main Results

1. Theorem 3.1: monotone cardinality online/streaming algorithm voi space `O(r)`, `O(mk)` evaluations, `O(m)` extra time; ratio it nhat `1/4`, tien dan den `0.3178`.
2. General cardinality line dat it nhat `1/8`, va tien dan den khoang `0.1589`.
3. Monotone partition matroid discrete algorithm dat asymptotic `0.3178`, matching streaming continuous-greedy results.
4. General partition matroid discrete algorithm dat it nhat `0.175` va tien dan den `0.1921`.
5. Appendix A.18 dua ra guarantee dau tien co y nghia cho individual knapsack constraints khi item sizes nho; monotone asymptotic cung muc `0.3178`.

## Core Algorithmic Idea

Khung cot loi cua paper la: moi part `a` co mot threshold / penalty `beta_a`, va item moi `t` duoc danh gia thong qua discounted marginal `w_(t,a) - beta_a`.

- Monotone cardinality: Algorithm 1 duy tri solution feasible va threshold cho tung part. Khi item moi den, tinh marginals, chon part co discounted gain lon nhat, va chen item neu discounted gain duong.
- Thay vi dung mot cong thuc dong nhat, paper cho phep he so rieng theo tung part va phan tich theo budget cua part do. Day giup xu ly budget imbalanced tot hon Ene-Nguyen 2022.
- General objectives: paper adapt algorithm trong regime budget khong qua lech, roi mo rong sang moi budget bang cach tao hai nghiem va lay nghiem tot hon; online version randomize giua hai nghiem.
- Knapsack: appendix chuyen sang density thresholds `rho = value / size` va dung mot ham lien tuc `g(u) = c e^{d u}` tren tong size da dung.

## Proof / Analysis Strategy

- Buoc 1: lower bound gia tri nghiem thuat toan `f(S)` bang mot primal potential, la to hop tuyen tinh cua weights hoac densities.
- Buoc 2: upper bound `f(S^*)` bang mot dual potential.
- Buoc 3: trong moi iteration, so sanh muc thay doi cua primal va dual; cong don qua toan bo stream se cho approximation guarantee.
- Buoc 4: chon cac tham so `d_a`, `c_a`, hoac subsampling probability `p` bang cach toi uu hoa upper bound tren tung part.

Chi tiet retrieval quan trong:

- monotone cardinality dan den phuong trinh `e^d - d - 2 = 0`, cho `d ~= 1.1461`, va asymptotic `0.3178`
- general cardinality can pairwise monotonicity-aware adaptation va two-solution reduction
- non-monotone partition matroid them subsampling, dan den asymptotic `0.1921`
- individual knapsack dung density-integral control, va khi item sizes nho thi cung hoi tu `0.3178`

## Key Techniques

- part-specific threshold coefficients
- primal/dual potential comparison
- tailored parameter choices cho budget imbalanced
- two-solution reduction cho non-monotone all-budgets case
- subsampling cho non-monotone partition matroid
- density-based continuous threshold for knapsack
- single-solution maintenance phu hop online free disposal

## Key Lemmas Or Structural Claims

- Theorem 3.1: monotone cardinality guarantee it nhat `1/4`, asymptotic `0.3178`.
- Theorem 3.2: general objective guarantee bang mot nua monotone guarantee trong regime budgets khong qua lech.
- Theorem A.9: reduction hai-nghiem mo rong general cardinality cho moi budget; asymptotic table summary la `0.1589`.
- Theorem A.10 / A.11: partition-matroid submodular discrete algorithms dat asymptotic `0.3178` monotone va `0.1921` general.
- Theorem A.18: monotone individual knapsack constraints voi item nho dat asymptotic `0.3178`.

## Delicate Points / Caveats

- Inbox file la arXiv 2023 preprint, nhung publication status da len AAAI 2025; canonical cua repo nen theo nam venue AAAI.
- Main body tap trung nhieu vao cardinality; knapsack va partition-matroid nam phan appendix nhung van la dong gop quan trong.
- Approximation guarantees "improve with budget" la thong tin retrieval rat quan trong cua paper.
- General `k`-submodular cardinality guarantee van thap hon offline line; paper danh vao online/streaming efficiency va breadth cua framework.

## Extraction To Concepts

- Bo sung vao `concepts/k-submodularity.md` rang constrained online/streaming line da co threshold tuning theo budget imbalanced, khong chi primal-dual dong nhat nhu Ene-Nguyen 2022.
- Reusable ingredient: two-solution reduction cho non-monotone khi mot budget qua lon so voi phan con lai.
- Reusable ingredient: density-threshold view cho individual knapsack khi item sizes nho.

## Extraction To Syntheses

- Cap nhat `syntheses/k-submodular.md` de danh dau paper nay nhu framework rong nhat hien co trong repo cho `online / streaming constrained` line.
- Trong synthesis nen phan biet ro:
  - Ene-Nguyen 2022: monotone per-coordinate cardinality, primal-dual version co ban
  - Spaeh-Ene-Nguyen 2025: framework rong hon, xu ly imbalance, non-monotone, partition-matroid, knapsack appendix
  - Pham et al. 2022 budgeted line: total-budget streaming voi cost-sensitive thresholding

## Weaknesses / Limits

- Tung ket qua rieng khong phai luc nao cung duoc trinh bay het trong main body; de bo sot appendix knapsack / partition-matroid.
- Du cai thien online/streaming state of the art, ratio van con khoang cach voi offline greedy / continuous-greedy line.

## Research Ideas Triggered

- Viet comparison note rieng giua `Ene-Nguyen 2022` va `Spaeh-Ene-Nguyen 2025`.
- Kiem tra xem density-based knapsack appendix co the ket hop voi heterogeneous-cost budgeted line cua Pham et al. 2022 hay khong.