# Submodular Synthesis

## Core Papers

- `Submodular Functions, Matroids, and Certain Polyhedra` (Edmonds):
  paper goc nen tang cho polymatroid / matroid / polyhedral viewpoint.
- `An Analysis of Approximations for Maximizing Submodular Set Functions - I` (Nemhauser, Wolsey, Fisher):
  paper goc cuc ky quan trong cho greedy approximation trong submodular maximization.
- `Submodular Function Minimization` (Iwata):
  survey diem vao tot cho minimization lineage.
- `A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time` (Schrijver):
  milestone cho exact minimization theory.
- `Streaming Submodular Maximization` (Badanidiyuru et al.):
  core paper cho streaming / massive-data direction.
- `The Fast Algorithm for Submodular Maximization` (Breuer, Balkanski, Singer):
  paper practical quan trong cho monotone cardinality parallel line, dua adaptive sequencing vao mot goi query-efficient co constants nho.
- `Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint` (Chen, Kuhnle):
  paper nen tang cho low-adaptivity non-monotone cardinality line, sua threshold-sampling cho non-monotone objectives va dat `1/6` / `0.193`.
- `Cardinality constrained submodular maximization for random streams` (Liu, Rubinstein, Vondrak, Zhao):
  moc random-order streaming, dat `1 - 1/e - epsilon` voi `O(k / epsilon)` memory cho monotone va `1 / e - epsilon` cho non-monotone, kem hardness barrier `1 - 1/e + epsilon`.
- `Optimal Submodular Maximization in Parallel` (Chen, Dey, Kuhnle):
  moc parallel monotone cardinality cho bo ba `LINEAR SEQ`, `THRESHOLD SEQ`, va `LS+PGB`, dat gan toi uu ve ratio / adaptivity / query complexity.
- `Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint` (Pham et al.):
  paper moc cho huong linear-query non-monotone knapsack.
- `Submodular Maximization in Exactly n Queries` (Balkanski, DiSilvio, Kuhnle, Peng):
  paper moc cho huong linear-query duoi matroid / p-matchoid, dung infeasible-set querying de dat exactly `n` va `2n` queries.
- `Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem` (Tran et al.):
  moc streaming trong minimum-cost submodular cover lineage.
- `Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint` (Tran et al.):
  moc low-adaptivity / parallel cho non-monotone knapsack.
- `Consistent Submodular Maximization` (Dutting et al.):
  paper mo nhanh stable / consistency-aware submodular maximization duoi cardinality, voi lower bound `2 - epsilon` cho deterministic constant-consistency algorithms.
- `Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization` (Chen, Nath, Peng, Kuhnle):
  moc ly thuyet cho combinatorial beyond-`1 / e`, dat `0.385` cho size va `0.305` cho matroid bang local-search guidance + guided greedy.
- `Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint` (Tukan, Mualem, Feldman):
  moc practical cho cardinality-constrained non-monotone line, dua ratio `0.385` ve query complexity `O(n + k^2)`.
- `Unconstrained Submodular Maximization in Dynamic Setting` (anonymous ICML 2026 submission):
  paper mo nhanh dynamic unconstrained non-monotone USM voi update-sublinear, pha moc `0.25` trong incremental va decremental, va dua ra mot fully dynamic bien the khi deletion times duoc reveal.
- `A General Framework for Dynamic Consistent Submodular Maximization` (anonymous ICML 2026 submission):
  paper day consistency line sang fully dynamic setting, cho cardinality va matroid, bang framework transition-window + deletion-robust subroutines.
- `Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation` (Chen, Chen, Kuhnle):
  moc parallel combinatorial moi cho size-constrained non-monotone line, khop moc `1 / e - epsilon` trong logarithmic adaptivity.

## Recurring Techniques

- greedy theo marginal gain
- thresholding / streaming thresholding
- adaptive sequencing
- binary search tren OPT va prefix positions trong parallel cardinality
- lazy updates cho marginal evaluations trong parallel settings
- cover-style logarithmic approximation
- SFM structural / strongly polynomial methods
- split-and-threshold cho non-monotone knapsack
- two-set threshold accounting cho non-monotone cardinality
- parallel / adaptive thresholding
- linear-query preprocessing + greedy boosting
- fast local search de tao guidance sets
- guided random greedy / guided interpolated greedy
- blended marginal-gain analysis cho interlaced solutions
- threshold sampling cho parallel interlaced greedy
- bicriteria cover guarantees
- random-window partitioning voi pooled reintroduction trong random-order streams
- querying vao infeasible supersets de tiet kiem value queries
- exchange-graph / gatekeeper arguments trong matroid analysis
- benchmark-set thresholding cho consistency-aware maintenance
- local-optimum chasing voi bounded swaps
- permanent-block plus fresh-buffer decomposition voi random half-sampling
- reverse-time buffer decomposition cho decremental USM
- randomized scheduling cua transition windows qua nhieu muc robustness
- deletion-robust subroutines + gradual migration giua hai loi giai
- hybrid threshold argument cho fully dynamic consistent cardinality

## Main Problem Settings

- maximization duoi cardinality va bien the gan voi cardinality
- maximization duoi matroid / p-matchoid khi query budget la tai nguyen chinh
- minimization trong oracle model
- cover / knapsack / constrained optimization
- streaming summarization
- practical low-adaptivity parallel cardinality maximization
- random-order streaming duoi cardinality constraints
- non-monotone knapsack trong linear-query va low-adaptivity regimes
- monotone cardinality maximization trong parallel linear-query regime
- non-monotone size / matroid maximization vuot moc `1 / e` bang combinatorial algorithms
- practical cardinality-constrained non-monotone maximization voi query budget rat thap
- minimum-cost submodular cover trong streaming setting
- dynamic insertion voi explicit consistency / stability guarantees
- unconstrained non-monotone USM trong dynamic models
- fully dynamic consistency-aware optimization duoi cardinality va matroid
- sublinear-adaptivity parallel algorithms cho non-monotone cardinality maximization
- dynamic models co deletion-time predictions / known deletion order

## Surveys and Entry Points

- bat dau voi Edmonds + Nemhauser-Wolsey-Fisher neu muon co foundations
- bat dau voi Iwata / McCormick neu muon vao minimization
- bat dau voi Liu et al. neu muon map greedy variants nhanh
- bat dau voi Pham et al. 2023 neu muon nhin nhanh tradeoff approximation-vs-query cho non-monotone knapsack
- bat dau voi Tran et al. 2023 neu muon vao cover lineage o che do streaming
- bat dau voi Balkanski et al. 2024 neu muon vao nhanh linear-query duoi matroid
- bat dau voi Breuer et al. 2019 neu muon vao nhanh practical parallel cardinality
- bat dau voi Dutting et al. 2024 neu muon vao nhanh consistency / stable solutions

## Open Directions

- ghep nhung note minimization thanh mot map ro hon
- tao comparison note cho cover lineage: Bar-Ilan -> Iyer-Bilmes -> Soma-Yoshida
- tao timeline cho greedy lineage: Nemhauser -> curvature surveys -> streaming
- tao comparison note cho non-monotone knapsack lineage: polynomial-query vs linear-query vs low-adaptivity parallel
- tao comparison note cho streaming lineage: adversarial-order `1/2` vs random-order `1 - 1/e`
- tao comparison note cho practical parallel cardinality line: FAST vs LTLG vs theory-first low-adaptivity algorithms
- tao comparison note cho linear-query line: knapsack vs matroid vs p-matchoid
- tao comparison note cho non-monotone constrained line: practical `0.385` size-only vs guided combinatorial size/matroid vs parallel `1 / e`
- kiem tra xem blended-marginal-gains / parallel interlaced machinery co mo rong duoc sang matroid hay knapsack khong
- lam ro khi nao querying infeasible sets that su can thiet de dat exactly-`n` query bounds
- mo rong consistency line sang matroid / knapsack / non-monotone settings va randomized algorithms
- cai thien moc `0.3` cho dynamic unconstrained USM, hoac bo gia thiet reveal deletion times trong fully dynamic variant
- thu hep khoang cach giua insertion-only consistency line va fully dynamic consistency line, dac biet duoi matroid constraints