# Tukan et al. 2024 - Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint

## One-paragraph Summary

Day la paper practical hoac "engineering-forward" cho non-monotone submodular maximization duoi cardinality constraint. Muc tieu cua paper khong phai mo them mot frontier ratio moi, ma la lay ratio `0.385` da biet la co the dat duoc va day no ve query complexity thuc dung `O(n + k^2)`. Spine cua paper co ba buoc: tim mot initial solution bang Sample Greedy lap lai, chay `FAST-LOCAL-SEARCH` de lay mot local optimum re, roi dung local optimum do de huong dan mot guided stochastic greedy step. Tra ve nghiem tot hon giua local-search candidate va guided-greedy candidate.

## Classification Rationale

Paper thuoc `submodular`, non-monotone, cardinality-constrained. Neu Chen et al. 2024 la moc ly thuyet rong hon cho size va matroid, thi Tukan et al. 2024 la moc practical chuyen biet cho size constraint voi query bound rat nhe. Hai paper co y tuong gan nhau o muc "guidance set", nhung paper nay day manh khia canh thuc nghiem va complexity thuc dung hon.

## Setup

- Objective: non-negative submodular maximization, khong gia su monotone.
- Constraint: `|S| <= k`.
- Access model: set-function value oracle.
- Prior baseline practical: `1 / e`.
- Target: ratio `0.385` voi query complexity thuc dung.

## Main Results

1. Co mot thuat toan `0.385`-approximation cho cardinality-constrained non-monotone submodular maximization.
2. Query complexity la `O(n + k^2)`, nhe hon ro so voi cac local-search / guided methods truoc.
3. `FAST-LOCAL-SEARCH` rieng le co query complexity `O(n + k^2)` va tra ve mot set thoa cac inequality local-optimum manh voi `OPT`.
4. Guided stochastic greedy step chi ton `O(n)` queries sau khi co local optimum.

## Core Algorithmic Idea

Algorithm chinh (Algorithm 3) gom:

1. Dung `Sample Greedy` lap lai `O(log 1 / epsilon)` lan de lay mot initial solution constant-factor.
2. Chay `FAST-LOCAL-SEARCH`:
   - moi iteration sample `n / k` phan tu;
   - tim mot phan tu vao co marginal lon nhat va mot phan tu ra co marginal nho nhat;
   - doi neu co loi;
   - lap nhieu attempt va chon mot intermediate set random thoa mot local optimality check.
3. Chay `Guided Stochastic Greedy` duoc tang toc boi y tuong tu Sample Greedy, co set `Z` tu local search lam guidance.
4. Tra ve `arg max{f(Z), f(A)}`.

## Proof / Analysis Strategy

- Theorem 3.1 cho thay local-search output `S` thoa cac inequality dang:
  `f(S) >= (f(S inter OPT) + f(S union OPT)) / (2 + epsilon)`
  va `f(S) >= f(S inter OPT) / (1 + epsilon)`.
  Day la phien ban nhanh cua classical local search guarantee.
- Theorem 3.2 phan tich guided stochastic greedy khi duoc cap mot set `Z` thoa cac inequality tren.
- Hai lower bound nay duoc ket hop trong Algorithm 3; mot nhanh bao phu khi local optimum da tot, nhanh kia bao phu khi guided stochastic greedy lay them gia tri tu residual optimum.
- Bai toan query complexity duoc ha bang hai cho:
  - local search chi sample `n / k` ung vien moi vong thay vi quet toan bo;
  - greedy improvement dung stochastic sampling thay vi random greedy full.

## Key Techniques

- repeated Sample Greedy de khoi tao
- accelerated local search
- guidance-set viewpoint
- accelerated stochastic greedy
- chon max giua local optimum va guided improvement

## Key Lemmas Or Structural Claims

- Theorem 3.1: `FAST-LOCAL-SEARCH` tao mot local optimum xap xi du manh trong `O(n + k^2)`.
- Theorem 3.2: guided stochastic greedy dat lower bound theo `OPT`, `OPT union Z`, `OPT inter Z`.
- Lemma 3.4: Algorithm 3 dat expected value `c - O(epsilon) - O(1 / k)` voi constant `c > 0.385`.
- Theorem 3.3: ket luan co `0.385`-approximation.

## Delicate Points / Caveats

- Paper chi xu ly cardinality constraint, khong xu ly matroid.
- Ratio `0.385` la theo expectation; diem practical la queries nhe, khong phai deterministic guarantee.
- Paper chu dong thua nhan co mot independent work gan nhu song song tren arXiv; quan he voi Chen et al. 2024 rat gan ve "guided local optimum" spine.

## Extraction To Concepts

- Chua can concept note rieng, nhung no nen duoc nhac trong synthesis duoi cum `practical beyond 1/e`.
- Reusable ingredient: accelerated local search voi sample `n / k`, kha khac voi local search truyen thong `O(nk^2)`.

## Extraction To Syntheses

- `syntheses/submodular.md` nen ghi paper nay la moc practical cho cardinality-constrained non-monotone line.
- Nen dat canh Chen et al. 2024 de tach ro ly thuyet rong hon vs thuat toan practical hon.

## Weaknesses / Limits

- Khong mo rong sang matroid hay parallel setting.
- Proof tiet kiem queries dua kha nhieu vao cardinality structure, nen khong ro chuyen truc tiep sang matroid duoc khong.