# Tang, Wang, Chan 2021 - Corrigendum to "On Maximizing a Monotone k-Submodular Function under a Knapsack Constraint"

## One-paragraph Summary

Day la corrigendum quan trong cho dong `monotone k-submodular knapsack`. File trong inbox thuc te chua ca corrigendum va ban letter goc; phan can canon la corrigendum. Tac gia xac nhan inequality (6) trong proof goc la sai, nhung dieu bat ngo la algorithm khong chet. Nguoc lai, voi mot revised proof, cung chinh algorithm enumeration-size-2 + density-greedy completion dat duoc ratio `0.4`, tot hon ca moc goc `1 / 2 - 1 / (2e) ~ 0.316`.

## Setup

- Objective: monotone non-negative `k`-submodular function `f`.
- Constraint: mot knapsack chung `c(S) <= B`, cost gan tren support, khong phu thuoc label.
- Algorithm: enumerate tat ca singleton / pair feasible, roi tu moi pair chay greedy theo mat do `Delta / c`.

## Main Results

1. Chi ro inequality (6) trong proof goc la sai.
2. Giu nguyen `Algorithm 2` cua paper goc.
3. Cung algorithm do dat `0.4`-approximation.
4. Query complexity van giu nhu line goc, cu the `O(n^4 k^3)` evaluations.

## Core Algorithmic Idea

- lay `SA` la singleton feasible tot nhat;
- enumerate moi pair feasible `Y` kich thuoc 2;
- tu `Y`, xet residual function `g(S) = f(S) - f(Y)` va chay density-greedy cho den khi knapsack het cho;
- output la nghiem tot nhat tren tat ca pair va singleton.

Phan moi nam o revised proof, khong nam o pseudocode.

## Proof / Analysis Strategy

- Chon `T` la optimum, sap xep cac item cua `T` theo thu tu marginal lon dan.
- Xet iteration ma algorithm doan dung seed `Y = G_2`, tuc hai item "dau" cua optimum.
- Goi `t* + 1` la buoc dau tien greedy muon them mot item thuoc optimum nhung bi knapsack chan.
- Dung mot claim kieu Ward-Zivny / Xiao rang residual optimum sau seed co the bi upper bound boi `2` lan gia tri cua mot nghiem greedy phu.
- Vi item reject dau tien lam vuot budget, partial greedy solution tai thoi diem do phai da "nuot" du cost cua residual. Ghep cac phan nay lai cho lower bound `2 / 5`.

## Key Techniques

- size-two seed enumeration
- marginal-density greedy
- residual function sau seed `Y`
- first rejected optimum item

## Delicate Points / Caveats

- Inbox PDF bundle ca corrigendum va original letter; canonical note nay uu tien corrigendum.
- Setting chi la monotone va single knapsack common-cost.
- Ket qua da bi vuot qua boi Wang 2025 trong monotone common-cost case (`1 / 2`), nhung corrigendum van quan trong ve mat lich su va proof hygiene.

## Extraction To Concepts

- Nen cap nhat `concepts/budgeted-k-submodular-maximization.md` de ghi ro chain corrigendum `0.4` -> Xiao 2023 -> Wang 2025.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen noi ro rang knapsack line co mot corrigendum quan trong.

## Weaknesses / Limits

- Khong xu ly non-monotone, multiple knapsacks, hay label-dependent costs.
- Enumeration va query complexity van rat nang.