# Xiao et al. 2023 - Approximation algorithms for k-submodular maximization subject to a knapsack constraint

## One-paragraph Summary

Day la paper combinatorial quan trong trong dong `k`-submodular knapsack, dac biet vi no la paper dau tien trong inbox xu ly ca monotone va non-monotone duoi mot knapsack chung bang greedy-type algorithms. Ket qua cua paper la:

- monotone: `1 / 2 (1 - e^-2) ~ 0.432`;
- non-monotone: `1 / 3 (1 - e^-3) ~ 0.317`.

So voi corrigendum cua Tang-Wang-Chan, paper nay nang monotone ratio tu `0.4` len `0.432`. So voi line ve sau cua Wang 2025, paper nay van quan trong vi no dua ra combinatorial non-monotone knapsack guarantee dau tien.

## Setup

- Objective: `k`-submodular `f`, co the monotone hoac non-monotone.
- Constraint: single knapsack `c(S) <= B` voi common item cost.
- Algorithm tham so boi `w`:
  - `w = 4` neu monotone;
  - `w = 7` neu non-monotone.

## Main Results

1. Monotone case dat `1 / 2 (1 - e^-2)` voi query complexity `O(n^6 k^5)`.
2. Non-monotone case dat `1 / 3 (1 - e^-3)` voi query complexity `O(n^9 k^8)`.
3. Day la guarantee dau tien cho non-monotone `k`-submodular knapsack bang greedy-type combinatorial algorithm.

## Core Algorithmic Idea

Algorithm 1 co dang:

- enumerate tat ca feasible seeds kich thuoc `w`;
- tu moi seed `s_0`, chay density-greedy, moi vong them cap `(e, i)` co `Delta_{e,i}(s) / c(e)` lon nhat;
- output nghiem tot nhat tren tat ca seeds.

Ly do phai enumerate seed co kich thuoc hang so la de trung hoa cac item "heavy but high-value" cua optimum, vi chi dua vao density-greedy tu rong co the bo lo chung.

## Proof / Analysis Strategy

Paper dung hai sequence dong thoi:

- `s_j`: partial greedy solution sau `j` buoc;
- `o_j`: transformed optimum gom support cua optimum goc va greedy partial solution.

Monotone:

- chung minh `f(o_{j-1}) - f(o_j) <= f(s_j) - f(s_{j-1})`;
- ket hop voi density threshold de giai mot recurrence kieu exponential;
- sau `w = 4` seed items, residual gap cho he so `1 / 2 (1 - e^-2)`.

Non-monotone:

- can inequality yeu hon `f(o_{j-1}) - f(o_j) <= 2 (f(s_j) - f(s_{j-1}))`;
- paper phai chung minh gain buoc greedy van khong am trong inequality nay;
- tu recurrence he so `2` nay suy ra `1 / 3 (1 - e^-3)` khi enumerate `w = 7`.

## Key Techniques

- constant-size seed enumeration
- density-greedy completion
- transformed optimum sequence
- recurrence residual-gap

## Delicate Points / Caveats

- Query complexity rat lon; gia tri cua paper chu yeu o approximation va proof combinatorial.
- Chi cho single knapsack common-cost.
- Monotone result bi vuot boi Wang 2025 (`1 / 2`), nhung paper nay van la moc quan trong do non-monotone result.

## Extraction To Concepts

- `concepts/budgeted-k-submodular-maximization.md` nen them moc `0.432` monotone va `0.317` non-monotone.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them paper nay vao knapsack line va recurring techniques `seed enumeration + density greedy`.

## Weaknesses / Limits

- Rat nang query.
- Khong xu ly label-dependent costs hay streaming.