1970 | foundational-original
Edmonds - Submodular Functions, Matroids, and Certain Polyhedra
Foundation của polyhedral viewpoint: polymatroid, base polyhedron, và greedy linear optimization.
SubResearch
Đây là trang tra cứu nhanh cho kho ghi chú nghiên cứu về submodular, k-submodular, và DR-submodular. Mục tiêu là mở một file và đi thẳng đến paper, summary, metadata, concept, hay synthesis cần xem.
Overview
Kho hien co 52 canonical papers da duoc dua len muc processed-deep, cung cac concept notes va synthesis notes de tai su dung.
52
canonical papers
23
submodular
27
k-submodular
2
DR-submodular
Quick Access
README.md
Workflow và cấu trúc repo ở mức tổng quan.
AGENTS.md
Hướng dẫn cho các thread Codex sau này.
inbox/intake-index.md
Map giữa file input và canonical folders.
templates/paper-note.md
Template cho deep canonical summary.
syntheses/submodular.md
Tổng hợp nhanh submodular.
syntheses/k-submodular.md
Tổng hợp nhanh k-submodular.
syntheses/dr-submodular.md
Tổng hợp nhanh DR-submodular.
concepts entry
Điểm vào nhanh cho cụm concept notes tái sử dụng.
Markdown Reader
Chưa mở file nào.
Click vào bất kỳ link `.md` nào trong trang để render ngay tại đây. Nếu trình duyệt chặn đọc file cục bộ qua `file://`, hãy mở repo bằng một local static server.
Priority Foundations
Hai paper gốc quan trọng nhất hiện nay là Edmonds 1970 và Nemhauser-Wolsey-Fisher 1978. Đây là hai điểm vào tốt nhất nếu cần tiếp tục deepen hoặc xây comparison notes.
Submodular Papers
Nhóm chính, gồm foundations, cover, minimization, constrained optimization, streaming, và surveys.
1970
Edmonds - Submodular Functions, Matroids, and Certain Polyhedra
Polyhedral foundation cho polymatroid và greedy linear optimization.
1978
Nemhauser, Wolsey, Fisher - Maximizing Submodular Set Functions
Greedy cardinality approximation và residual-gap proof spine kinh điển.
2001
Bar-Ilan, Kortsarz, Peleg - Generalized Submodular Cover Problems and Applications
Reduction framework cho generalized cover và các ứng dụng graph / center selection.
2000
Schrijver - A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
Strongly polynomial SFM qua base polyhedron và exchange-style certificate.
2007 | survey
Iwata - Submodular Function Minimization
Landing survey cho SFM, discrete convexity, Lovasz extension, và combinatorial minimization.
2007 | survey
McCormick - On Submodular Function Minimization
Tutorial-style survey để định vị nhanh minimization và chọn paper gốc cần đọc tiếp.
2013
Iyer and Bilmes - Submodular Optimization with Submodular Cover and Knapsack Constraints
Framework cho SCSC / SCSK, surrogate modular bounds, và constrained submodular optimization.
2014
Badanidiyuru et al. - Streaming Submodular Maximization
`Sieve-Streaming`, one-pass thresholding, và approximation `1/2 - epsilon`.
2019
Breuer, Balkanski, Singer - The Fast Algorithm for Submodular Maximization
`FAST` dua adaptive sequencing vao cardinality parallel line de dat `1 - 1 / e - epsilon` voi `O(n log log k)` queries va nhan manh practical runtime.
2020 | survey
Liu et al. - Submodular Optimization Problems and Greedy Strategies: A Survey
Bản đồ cho curvature, batched greedy, string submodularity, và greedy lineage mở rộng.
2020
Chen and Kuhnle - Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
`ThreshSeq`, `AST`, va `ATG` sua threshold-sampling cho non-monotone cardinality, dat `1/6 - epsilon` va `0.193 - epsilon` voi near-linear queries.
2021
Liu et al. - Cardinality constrained submodular maximization for random streams
Random-order streaming cardinality line: `1 - 1/e - epsilon` cho monotone, `1/e - epsilon` cho non-monotone, kem hardness barrier `1 - 1/e + epsilon`.
2021
Chen, Dey, Kuhnle - Optimal Submodular Maximization in Parallel
`LINEAR SEQ`, `THRESHOLD SEQ`, va `LS+PGB` dat monotone cardinality gan-toi-uu trong `O(log n)` adaptivity va expected `O(n)` queries.
2023
Pham et al. - Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
`DLA` va `RLA` dua non-monotone knapsack ve linear-query regime voi cac factor `6 + epsilon` va `4 + epsilon`.
2023
Tran et al. - Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem
`StrMSC` dat bicriteria streaming near-linear cho minimum-cost submodular cover.
2024
Chen et al. - Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization
Moc combinatorial beyond-`1 / e` cho non-monotone size va matroid, dung fast local search + guided greedy de dat `0.385` va `0.305`.
2024
Tukan et al. - Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint
Huong practical cho non-monotone cardinality, dua ratio `0.385` ve query complexity `O(n + k^2)` bang fast local search + guided stochastic greedy.
2024
Balkanski et al. - Submodular Maximization in Exactly n Queries
`QuickSwap` / `QuickSwapNM` day matroid-constrained submodular maximization vao exactly-`n` va `2n` query regime, kem mo rong `p`-matchoid.
2024
Dutting et al. - Consistent Submodular Maximization
`Encompassing-Set` va `Chasing-Local-Opt` mo nhanh stable / consistency-aware cardinality maximization trong insertion streams.
2026
Anonymous - Unconstrained Submodular Maximization in Dynamic Setting
Mo nhanh dynamic unconstrained non-monotone USM, pha moc `0.25` voi amortized `O(sqrt(n))` queries trong incremental / decremental, va them bien the fully dynamic khi deletion times duoc reveal.
2025
Chen et al. - Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation
Moc parallel combinatorial cho non-monotone cardinality: `PIG` dat `(1/4 - epsilon)` va `PITG` dat `1 / e - epsilon` trong logarithmic adaptivity.
2026
Anonymous - A General Framework for Dynamic Consistent Submodular Maximization
Framework fully dynamic cho consistency-aware submodular maximization duoi cardinality va matroid, dung transition windows va deletion-robust routines de dat sublinear consistency.
2024
Tran et al. - Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint
`AST` cai thien huong low-adaptivity cho non-monotone knapsack len `7 + epsilon` trong `O(log n)` rounds.
k-Submodular
2013
Huber and Kolmogorov - Towards Minimizing k-Submodular Functions
Paper nen tang cho minimization / polyhedral line: Min-Max theorem, unified vectors, `P(f)`, va nut that good characterization trong oracle model.
2013
Gridchyn and Kolmogorov - Potts model, parametric maxflow and k-Submodular Functions
Noi Potts partial-optimality preprocessing voi `k`-submodular relaxations, va giam Kovtun preprocessing xuong `ceil(1 + log_2 k)` maxflow calls.
2014
Ward and Zivny - Maximizing k-Submodular Functions
Paper mốc cho approximation của bisubmodular và k-submodular maximization trong oracle model.
2015
Iwata, Tanigawa, Yoshida - Improved Approximation Algorithms for k-Submodular Function Maximization
Paper cot loi cua maximization line: dat `1/2` cho unconstrained, `k / (2k - 1)` cho monotone, va hardness asymptotic tight cho monotone case.
2016
Hirai and Iwamasa - On k-Submodular Relaxation
Characterizes khi nao multilabel objective admit `k`-submodular relaxation qua `theta`-closure, kem construction `O((kn)^2)`, half-integrality, va binary maximality.
2016
Sakaue - On maximizing a monotone k-Submodular Function subject to a Matroid Constraint
Greedy combinatorial `1/2`-approximation cho monotone matroid-constrained line.
2017
Hirai and Oki - A compact representation for minimizers of k-Submodular Functions
Dua minimizer sets ve elementary PIP / median-semilattice representation, kem Potts-specific enumeration cua maximal minimizers.
2017
Oshima - Derandomization for k-Submodular Maximization
Derandomize baseline monotone `k / (2k - 1)` bang distribution-support LP updates va output tot nhat trong support.
2018
Soma - No-regret algorithms for online k-Submodular Maximization
Mo nhanh online-learning branch: no-`1/2` regret va no-`k / (2k - 1)` regret qua selection games + Blackwell approachability.
2020
Rafiey and Yoshida - Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints
Mo nhanh privacy line cho monotone `k`-submodular matroid, dat private `1/2`, song hanh voi private continuous-greedy `(1 - 1/e)` cho submodular.
2021
Oshima - Improved Randomized Algorithm for k-Submodular Function Maximization
Lam sac dong unconstrained non-monotone bang refined randomized assignment, dat `(k^2 + 1) / (2k^2 + 1)` va ratio dac biet tot hon cho `k = 3`.
2021
Zheng et al. - Maximizing Approximately k-Submodular Functions
Dinh nghia `eps`-approximately `k`-submodular / `eps`-ADR va phan tich greedy duoi total-size va individual-size cho objectives xap xi / noisy.
2021 | corrigendum
Tang, Wang, Chan - Corrigendum to "On Maximizing a Monotone k-Submodular Function under a Knapsack Constraint"
Sua proof cua ORL knapsack line va nang ratio cua cung algorithm size-two-seed + density-greedy len `0.4`.
2021
Huang, Wang, Zhou - On Optimal Approximations for k-Submodular Maximization via Multilinear Extension
Paper continuous / Frank-Wolfe cho `k`-multilinear extension, dat `1/2 - epsilon` va `1/3 - epsilon` cho single matroid hay `O(1)` knapsacks.
2022
Pham et al. - Maximizing k-Submodular Functions under Budget Constraint: Applications and Streaming Algorithms
Budgeted / total-budget streaming cho `k`-submodular, xu ly ca cost chung va cost phu thuoc label, voi guarantees cho ca monotone va non-monotone.
2022
Ene and Nguyen - Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints
Primal-dual single-pass cho per-coordinate cardinality, online free disposal, va ratio tang theo `B_min` den xap xi `0.2953`.
2022
Pham et al. - Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint
`FSA` va `IFSA` cho monotone k-submodular knapsack: `1/10` single-pass `O(nk)` va `1/4 - epsilon` multi-pass `O(nk / epsilon)`.
2023
Nie et al. - Size-Constrained k-Submodular Maximization in Near-Linear Time
Threshold-greedy near-linear cho total-size va individual-size, giu cac ratio `(1/2 - epsilon)` va `(1/3 - epsilon)` ma khong con phu thuoc tuyen tinh vao budget.
2023
Niu et al. - Fast algorithms for k-Submodular Maximization subject to a Matroid Constraint
Threshold-decreasing duoi matroid, giu moc `(1/2 - epsilon)` va `(1/3 - epsilon)` ma bo phu thuoc tuyen tinh vao rank cua greedy.
2023
Wang et al. - Streaming Algorithms for the k-Submodular Cover Problem
Huong cover / bicriteria streaming cho `k`-submodular, voi known-guess, 2-pass, va 1-pass algorithms.
2023
Tran et al. - Maximizing a k-Submodular Maximization Function under an Individual Knapsack Constraint
Ban conference SoICT mo nhanh `kSMIK` va threshold streaming duoi budget rieng cho tung label.
2023
Xiao et al. - Approximation algorithms for k-submodular maximization subject to a knapsack constraint
Day common-cost single-knapsack line len `0.432` cho monotone va dua ra greedy-type `0.317` dau tien cho non-monotone.
2024
Zhu, Basu, Pavan - Fairness in Monotone k-Submodular Maximization
Huong fairness exact duoi total budget, dat `1/3` voi greedy va `(1/3 - epsilon)` voi threshold version.
2025
Spaeh, Ene, Nguyen - Online and Streaming Algorithms for Constrained k-Submodular Maximization
Framework online/streaming rong cho cardinality va knapsack, xu ly ca monotone lan general objectives va ratio cai thien khi budget lon.
2025
Wang - A 1/2-Approximation for Budgeted k-Submodular Maximization
`1-Guess Greedy` dat moc combinatorial `1/2` cho monotone total-budget knapsack va `1/3` cho non-monotone, bang continuous transformation qua `k`-multilinear extension.
2025
Tran et al. - k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm
Ban journal APJOR mo rong nhanh `kSMIK`, them phan tich non-monotone va hai-pass deterministic streaming.
2026 | draft
Anonymous - Fairness k-Submodular Maximization subject to Matroid Constraint
Mo rong fairness sang matroid va non-monotone objectives, nhung lower bounds chi duoc dam bao o muc `floor(l_i / 2)`.
DR-Submodular
2015
Soma and Yoshida - A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice
Generalized cover trên integer lattice với decreasing-threshold algorithm và bicriteria guarantee.
2026
Tran and Pham - Fast Approximation Algorithm for Non-monotone DR-submodular Maximization under Size Constraint
`FastDrSub` va `FastDrSub+` dua deterministic near-linear-time guarantees vao non-monotone DR-submodular size-constrained maximization.
Important Concept Notes
submodularity.md
Định nghĩa và trực giác gốc cho set-submodularity.
polymatroid.md
Polyhedral / rank-function viewpoint, nối trực tiếp với Edmonds.
greedy-cardinality-approximation.md
Greedy lineage bắt đầu từ Nemhauser-Wolsey-Fisher.
submodular-function-minimization.md
Cửa sổ vào nhanh SFM và các family thuật toán.
linear-query-submodular-maximization.md
Khung nhanh cho query-efficient / exactly-`n` submodular maximization.
consistent-submodular-maximization.md
Consistency, stability, va dynamic insertion viewpoint cho submodular maximization.
k-submodularity.md
Khung assignment-domain cho k-submodular / bisubmodular.
k-submodular-relaxation.md
Entry point nhanh cho relaxations, persistency, va partial optimality trong multilabel `k`-submodular line.
approximate-k-submodularity.md
Robust / noisy-objective viewpoint cho approximate `k`-submodularity va exact-proxy transfer.
budgeted-k-submodular-maximization.md
Entry point nhanh cho total-budget, streaming, va individual-knapsack line cua `k`-submodular maximization.
fair-k-submodular-maximization.md
Khung nhanh cho fairness duoi total budget va matroid, kem distinction giua exact fairness va fairness approximation.
k-submodular-min-max-theorem.md
Min-Max / polyhedral viewpoint cho k-submodular minimization.
dr-submodularity-on-integer-lattice.md
Diminishing returns trên integer lattice và relation với cover.
non-monotone-submodular-knapsack.md
Entry point nhanh cho tradeoff approximation, query complexity, va adaptivity trong non-monotone knapsack.
submodular-cover.md
Khung nhanh cho cover lineage: greedy cost-per-gain, bicriteria, streaming, va generalized variants.