# Tran and Pham 2026 - Fast Approximation Algorithm for Non-monotone DR-submodular Maximization under Size Constraint

## One-paragraph Summary

Day la paper DR-submodular quan trong vi no dua mot line "fast deterministic approximation" vao bai toan non-monotone DR-submodular maximization duoi size constraint. Paper de xuat hai thuat toan: `FastDrSub`, dat ratio xap xi `0.044` trong `O(n log k)` queries, va `FastDrSub+`, dat `1/4 - epsilon` trong `O((n/epsilon) log(1/epsilon) log k)` queries. Dong gop lon nhat khong phai ratio dep hon ly thuyet tot nhat, ma la dat constant-factor deterministic guarantees trong regime near-linear-time cho integer lattice.

## Classification Rationale

Paper thuoc `dr-submodular` vi no lam viec tren integer lattice va dung diminishing returns theo nghia lattice, khong phai set-submodular hay assignment-domain. No rat hop de doc sau paper `Soma-Yoshida 2015` vi cho thay nhanh DR-submodular da dich tu monotone cover sang non-monotone maximization.

## Setup

- Domain / model: DR-submodular function tren integer lattice.
- Constraint: size constraint, co the hieu la tong so luong / mass tren lattice bi chan boi `k`.
- Oracle / access model: oracle cho `f` tren lattice points.
- Goal: dat deterministic approximation nhanh thay vi dua vao reductions / randomization chi co ratio dep nhung query nang hon.

## Main Results

1. `FastDrSub` la coarse deterministic routine dat ratio xap xi `0.044` trong `O(n log k)` queries.
2. `FastDrSub+` dung output cua `FastDrSub` de xac dinh range cua optimum va nang ratio len `1/4 - epsilon`.
3. Paper nhan manh rang day la deterministic alternative trong mot boi canh nhieu ket qua nhanh truoc do dua vao randomization hoac reduction sang submodular knapsack.

## Core Algorithmic Idea

Paper co hai pha ro rang.

Pha dau, `FastDrSub` tach domain / optimum thanh hai phan va xay hai candidates trong hai subspaces khac nhau. Y tuong la tren integer lattice non-monotone, co the khoan vung duoc phan optimum ma tung candidate co the "gianh". Sau do paper merge hai candidates de lay mot nghiem co ratio nho nhung on dinh.

Pha hai, `FastDrSub+` xem `FastDrSub` nhu mot coarse estimator cho `OPT`, roi chay them mot threshold-guessing framework inspired by fast submodular-knapsack algorithms. Day la ly do paper nhac truc tiep toi `Badanidiyuru-Vondrak 2014` va line fast non-monotone submodular knapsack.

## Proof / Analysis Strategy

- Buoc 1: chung minh mot vai bat dang thuc DR-submodular / lattice-submodular co the dung de tach optimum thanh hai phan `o1, o2`.
- Buoc 2: phan tich hai candidates `x, y` cua `FastDrSub`, va dung lemmas kieu `f(o1 v x) + f(o1 v y) <= 4(f(x) + f(y))` de absorb gia tri optimum.
- Buoc 3: optimize tham so `alpha` trong `FastDrSub` de ra he so xap xi `0.044`.
- Buoc 4: dung output cua `FastDrSub` de dat upper/lower bound cho `OPT`, roi threshold-guess trong `FastDrSub+` de nang ratio len gan `1/4`.

## Key Techniques

- partition optimum / domain thanh hai subspaces
- deterministic thresholding tren integer lattice
- plus-version dung coarse constant-factor output de guess optimum
- hoc DNA tu fast submodular knapsack nhung chuyen sang DR-submodular

## Key Lemmas Or Structural Claims

- Co mot he bat dang thuc cho hai candidates tren lattice giup chan phan optimum thuoc mot subspace boi tong gia tri hai candidates.
- Phan con lai cua optimum duoc chan boi selection rule threshold.
- Toi uu hoa tham so `alpha` cho `FastDrSub` dan toi ratio xap xi `0.044`.
- `FastDrSub+` ke thua lower bound cua `FastDrSub` de dam bao co mot threshold guess nam gan optimum.

## Delicate Points / Caveats

- Ratio `0.044` cua `FastDrSub` nho, nhung paper co y dung no nhu building block cho `FastDrSub+`.
- Paper nhan manh "deterministic near-linear-time" hon la "best approximation".
- File intake la journal article 2026; mot phien ban arXiv 2025 co ve ton tai, nhung canonical note nen gan theo journal version nay.

## Extraction To Concepts

- Cap nhat `concepts/dr-submodularity-on-integer-lattice.md` voi nhanh non-monotone size-constrained.
- Technique lap lai: dung coarse fast routine de support plus-version tren lattice.
- Quan he voi nhom khac: paper nay noi rat ro voi line fast non-monotone submodular knapsack trong `submodular`.

## Extraction To Syntheses

- Cap nhat `syntheses/dr-submodular.md` de bo sung nhanh non-monotone / size constraint.
- Co the nhac paper nay trong `syntheses/submodular.md` nhu mot minh hoa cho viec ky thuat fast-thresholding duoc chuyen sang lattice domains, nhung khong bat buoc.

## Weaknesses / Limits

- `FastDrSub` co ratio kha nho neu dung mot minh.
- `FastDrSub+` tot hon nhung van thua cac ket qua ratio cao hon neu chap nhan polynomial-query hoac randomized frameworks.
- Paper can mang theo bo notation lattice, de doc hon cac paper set-submodular.

## Research Ideas Triggered

- So sanh reduction tu DR-submodular sang submodular knapsack voi khung combinatorial truc tiep cua paper nay.
- Tim xem small-factor coarse routine co the duoc dung cho cac DR-submodular constraints khac ngoai size constraint hay khong.