# Tran et al. 2024 - Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint

## One-paragraph Summary

Neu paper IJCAI 2023 tap trung vao linear-query offline, thi paper IJCAI 2024 nay dich chuyen sang mot truc hieu nang khac: `adaptivity`. Dong gop chinh la `AST`, mot thuat toan song song cho non-monotone submodular maximization duoi knapsack, dat factor `7 + epsilon` trong `O(log n)` adaptive rounds va query complexity `O~(nk)`. Gia tri cua paper nam o cho no cai thien factor cua huong near-optimal adaptivity ma van giu duoc tinh song song manh.

## Classification Rationale

Paper thuoc `submodular` vi setting van la set-submodular knapsack. No giao thoa manh voi `parallel algorithms`, `adaptivity`, `non-monotone`, va la buoc tiep theo rat tu nhien sau paper linear-query 2023 trong cung line non-monotone knapsack.

## Setup

- Domain / model: nonnegative non-monotone submodular set function.
- Oracle / access model: parallel value-oracle model; metric hieu nang la `adaptivity`, tuc so round query phu thuoc lan nhau.
- Constraint: mot knapsack constraint.
- Goal: giu query complexity va adaptivity thap nhung cai thien approximation factor so voi cac paper near-optimal adaptivity truoc do.

## Main Results

1. Paper dua ra `AST`, mot `(7 + epsilon)`-approximation cho non-monotone SMK.
2. `AST` dat `O(log n)` adaptivity va `O~(nk)` query complexity, cai thien factor so voi paper near-optimal adaptivity truoc do co factor `8 + epsilon`.
3. Thuc nghiem tren Revenue Maximization, Image Summarization, va Maximum Weighted Cut cho thay loi the thuc dung ve song song ma khong hy sinh qua nhieu quality.

## Core Algorithmic Idea

Paper dua ra mot khung moi goi la `alternate threshold`. Thay vi chi xay mot candidate solution bang parallel threshold sampling, `AST` luan phien xay hai nghiem roi nhau `X` va `Y`. Muc tieu la trong setting non-monotone, hai nghiem roi nhau nay co the "chia" residual optimum theo cach de control hon.

`AST` dung mot subroutine adaptivity-thap de lay mot coarse lower bound truoc, roi tu do guess threshold schedule. Tren tap phan tu cost nho, no chay cac round alternate-threshold theo density rule. Phan cost lon va singleton-like cases duoc xu ly rieng de tranh bo sot optimum thong tri boi phan tu lon.

## Proof / Analysis Strategy

- Buoc 1: dung mot subroutine song song co san de lay lower bound constant-factor va de guess optimum.
- Buoc 2: tach small-cost / large-cost elements de co the threshold tren phan "de parallel hoa" ma khong mat control doi voi heavy elements.
- Buoc 3: phan tich quan he giua hai nghiem `X, Y` sau moi round alternate threshold; day la lemmas trung tam de cho thay tong gain cua hai nghiem absorb duoc interaction non-monotone.
- Buoc 4: ket hop output cua pha alternate-threshold voi heavy-element fallback va lower-bound guesses de suy ra factor cuoi cung `7 + epsilon`.

## Key Techniques

- adaptivity lam metric trung tam
- alternate threshold framework
- parallel threshold sampling / density filtering
- hai candidate disjoint cho non-monotone case
- small-vs-large cost decomposition

## Key Lemmas Or Structural Claims

- Mot lower bound coarse co the duoc lay trong `O(log n)` adaptivity bang subroutine song song co san.
- Sau moi round, cau truc disjoint cua `X` va `Y` giu duoc mot bat dang thuc then chot giua gain hien tai va residual optimum.
- Heavy elements duoc tach rieng de khong lam vo phan tich threshold tren phan con lai.

## Delicate Points / Caveats

- Paper toi uu `adaptivity`, khong phai query complexity tuyet doi. Neu moi truong khong can song song, paper 2023 linear-query co the hop hon.
- Factor `7 + epsilon` van xa best-known approximation polynomial-query.
- Phan notation va cac subroutine reused tu literature song song kha day dac; can doc spine `lower bound -> alternate threshold -> combine heavy case` de khong bi lac.

## Extraction To Concepts

- Cap nhat `concepts/non-monotone-submodular-knapsack.md` voi truc query-vs-adaptivity.
- Technique lap lai: duy tri hai nghiem disjoint trong song song de giam anh huong non-monotonicity.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` trong nhanh non-monotone knapsack va adaptive / parallel direction.

## Weaknesses / Limits

- Khong canh tranh ve approximation voi cac thuat toan query-nang hon.
- Phu thuoc vao mot chuoi subroutine va lemmas adaptivity tu van hoc truoc, nen barrier de doc cao hon paper 2023.

## Research Ideas Triggered

- So sanh ro hon giua `DLA/RLA` 2023 va `AST` 2024: query complexity, adaptivity, va muc ratio dat duoc.
- Kiem tra xem alternate-threshold co the chuyen sang cover hay DR-submodular reductions khong.