# Pham et al. 2023 - Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

## One-paragraph Summary

Day la paper tap trung truc tiep vao tradeoff giua approximation factor va so luong oracle queries cho non-monotone submodular maximization duoi mot knapsack. Dong gop chinh khong nam o viec vuot qua best-known approximation ratio, ma o viec dua hai thuat toan constant-factor xuong muc linear-query theo `n`: `DLA` dat factor `6 + epsilon`, con `RLA` dat factor `4 + epsilon`, ca hai deu co query complexity `O(n log(1/epsilon) / epsilon)`. Paper vi vay la mot moc quan trong cho huong "fast but still provable" trong non-monotone knapsack.

## Classification Rationale

Paper thuoc `submodular` vi no lam viec tren set functions co tinh non-monotone, khong co assignment-domain hay lattice-domain. No giao thoa manh voi `knapsack`, `non-monotone maximization`, `query-efficient algorithms`, va la mot paper rat hop de doc cung cac huong adaptive / parallel sau nay.

## Setup

- Domain / model: nonnegative non-monotone submodular set function `f : 2^V -> R_+`.
- Oracle / access model: value oracle; metric hieu nang chinh la so lan query `f`.
- Constraint: mot knapsack constraint voi cost modular `c(S) <= B`.
- Assumptions: paper tap trung vao offline oracle model, khong phai streaming hay adaptive model.

## Main Results

1. Paper dua ra `LA`, mot coarse deterministic building block co factor `19` trong `O(n)` queries, va dung no de khoa range / candidate structure cho cac thuat toan tot hon.
2. `DLA` la deterministic linear-query algorithm dat factor `6 + epsilon` trong `O(n log(1/epsilon) / epsilon)` queries.
3. `RLA` la randomized linear-query algorithm dat factor `4 + epsilon` trong cung bac query complexity, matching huong "fastest constant-factor randomized" nhung bo he so `log k` khi `k` co the lon.

## Core Algorithmic Idea

Y tuong cot loi cua paper la tach bai toan non-monotone knapsack thanh mot so candidate structures co the xu ly bang linear-query thresholding.

`LA` chia ground set thanh hai mien dua tren cost. Mot mien duoc xu ly bang singleton / small candidate, mien con lai duoc xu ly bang threshold rule de thu mot nghiem coarse trong chi phi query tuyen tinh. Du factor `19` con yeu, `LA` rat quan trong vi no la "cheap lower bound" va cho khung de re-scan.

`DLA` nang cap `LA` bang cach xay hai candidate solutions roi nhau, ket hop threshold greedy voi mot pha quet lai cac phan tu "tot" de tranh viec non-monotonicity pha vo cau truc greedy mot duong.

`RLA` tiep tuc random hoa buoc ket hop / chon phan tu giua cac candidate roi nhau. Randomization o day khong de tim ratio ly thuyet tot nhat tuyet doi, ma de sua tradeoff giua gain hien tai va loss doi voi residual optimum ma van giu query budget gan tuyen tinh.

## Proof / Analysis Strategy

- Buoc 1: xay lower-bound coarse trong `O(n)` queries thong qua `LA`, chu yeu bang cost splitting va threshold acceptance.
- Buoc 2: doi voi `DLA`, phan tich hai candidate disjoint va cho thay mot trong hai buoc threshold / rescan buoc optimum roi vao mot trong cac case co the control duoc.
- Buoc 3: doi voi `RLA`, phan tich ky vong cua gain khi random hoa giua cac candidate structures, tuong tu exchange-in-expectation nhung dat trong boi canh knapsack thresholding.
- Buoc 4: cong don cac bound tren residual optimum va singleton / threshold candidates de ra factor cuoi cung.

## Key Techniques

- chia ground set theo cost de tao lower bound coarse
- threshold greedy voi so query tuyen tinh
- duy tri hai nghiem roi nhau de doi pho non-monotonicity
- randomize giua candidate sets de cai thien factor ma khong tang query complexity bac lon
- dung coarse linear-query routine lam building block cho thuat toan tot hon

## Key Lemmas Or Structural Claims

- `LA` co the tra ve mot lower bound constant-factor trong chi `O(n)` queries.
- Neu mot candidate solution co tong cost gan budget thi no tu dong khoa duoc mot phan gia tri lon cua optimum.
- Khi duy tri hai nghiem disjoint, tong gain tren hai nghiem co the absorb phan loss do non-monotone interactions gay ra.
- Randomization giua candidate structures giup doi expectation cua solution quality lay duoc factor `4 + epsilon`.

## Delicate Points / Caveats

- Paper dung "approximation factor" theo kieu `c + epsilon`, nghia la gia tri dat duoc xap xi `OPT / (c + epsilon)`, khong phai ratio lon hon 1.
- `LA` khong phai diem dung cuoi cung; no chu yeu la mach phu tro cho `DLA` va `RLA`.
- Thuat toan nhanh hon ro ret ve query complexity nhung khong co muc ratio tot nhat ly thuyet so voi cac thuat toan polynomial-query.
- Paper khong giai quyet adaptivity / parallelism; muc tieu cua no la linear-query offline.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: non-monotone submodular knapsack trong regime linear-query.
- Lemma co the tai su dung: coarse constant-factor lower bound co query complexity tuyen tinh de khoa threshold grid / candidate rescans.
- Technique lap lai: split-and-threshold tren hai nghiem roi nhau cho non-monotone knapsack.
- Quan he voi nhom khac: la tien de tot cho paper adaptive / parallel 2024 va cho reduction duoc nhac trong DR-submodular 2026.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` trong cum non-monotone knapsack / fast algorithms.
- Tao concept note rieng cho `non-monotone-submodular-knapsack.md` la hop ly vi paper nay se dung lai.

## Weaknesses / Limits

- Factor `6 + epsilon` va `4 + epsilon` van thua xa best-known approximation polynomial-query.
- Paper chu yeu toi uu query complexity; neu query khong phai nut that thi cac thuat toan cham hon co the dep hon ve ratio.
- Chi xu ly mot knapsack, khong mo rong truc tiep sang nhieu budget categories hay richer constraints.

## Research Ideas Triggered

- So sanh "linear-query offline" cua paper nay voi huong adaptive parallel de xem phan nao la tradeoff giua query va adaptivity.
- Kiem tra xem coarse routine `LA` co the dung nhu subroutine cho cac reduction DR-submodular / lattice-submodular khong.