# Iyer and Bilmes 2013 - Submodular Optimization with Submodular Cover and Knapsack Constraints

## One-paragraph Summary

Paper nay quan trong vi no day rang buoc tu "de" sang "kho": thay vi cardinality hay modular knapsack, no cho ca objective va constraint deu mang tinh submodular. Hai bai toan trung tam la submodular cost submodular cover (SCSC) va submodular cost submodular knapsack (SCSK). Paper vua dua ra hardness, vua de xuat cac thuat toan dua tren modular bounds va ellipsoidal approximations, va qua do cho thay mot cau noi ro rang giua constrained submodular optimization va difference-of-submodular motivations trong machine learning.

## Classification Rationale

Paper nam trong `submodular` va giao thoa giua `cover`, `knapsack`, `constrained optimization`, va `difference-of-submodular`. No rat phu hop de dat gan cover literature, nhung nen duoc danh dau la mot paper giao thoa vi rang buoc va cost deu la submodular.

## Setup

- Domain / model: hai ham submodular tren tap, thuong mot ham dong vai tro utility / cover va mot ham dong vai tro cost.
- Oracle / access model: value oracle cho cac ham, ket hop voi surrogate modular / ellipsoidal de thuc thi thuat toan.
- Assumptions: quan tam chu yeu den truong hop don dieu; cac bai toan la SCSC (toi thieu cost de dat utility muc tieu) va SCSK (toi da utility duoi ngan sach submodular).

## Main Results

1. Paper chinh thuc hoa va phan tich hai bai toan SCSC va SCSK, tong quat hoa cover va knapsack submodular quen thuoc.
2. No dua ra cac xap xi / bicriteria dua tren modular lower-upper bounds va ellipsoidal approximations, cung voi hardness gan nhu khop toi log-factors.
3. Paper chi ra quan he giua hai bai toan thong qua reductions / wrappers, nen mot algorithm cho mot ben co the chuyen thanh algorithm cho ben kia.

## Core Algorithmic Idea

Phan kho cua paper la rang buoc / cost submodular lam cho greedy truyen thong khong con dung truc tiep. Cach xu ly la thay ham submodular bang cac surrogate de hon: modular lower bounds de giu phia utility, modular upper bounds de kiem soat cost, va ellipsoidal approximations de dua ve bai toan da quen thuoc hon. Sau do, paper lap cac quy trinh iterative de giai surrogate, cap nhat bound, va lap lai cho den khi thu duoc nghiem kha.

## Proof / Analysis Strategy

- Buoc 1: phan tich hardness va chi ra rang neu de nguyen bai toan o dang submodular-submodular thi khong the hy vong ratio qua tot.
- Buoc 2: dung modular / ellipsoidal surrogates de "kep" bai toan goc giua cac bai toan de xu ly hon, roi ap dung greedy / knapsack-style subroutines.
- Buoc 3: chung minh sai so do surrogate tao ra chi lam mat mot he so co kiem soat, tu do suy ra approximation hoac bicriteria bounds cho bai toan goc.

## Key Techniques

- modular lower bounds cho submodular functions
- modular upper bounds / superdifferential-style surrogates
- ellipsoidal approximation
- reductions giua SCSC va SCSK

## Key Lemmas Or Structural Claims

- Cac surrogate modular co the kep ham submodular tu duoi / tu tren du chat de tai su dung cho cover / knapsack.
- Giai mot bai toan surrogate co the chuyen thanh nghiem xap xi cho bai toan goc voi mat mat chi trong he so phu thuoc curvature / log.
- SCSC va SCSK co quan he giam tru / goi lap nhau, nen ket qua mot ben co the dung lam hop den cho ben kia.

## Delicate Points / Caveats

- Day khong phai paper ve mot clean greedy theorem duy nhat; no la paper framework voi nhieu surrogate va wrappers, nen can giu ro vai tro cua tung lop approximation.
- Can phan biet bound ly thuyet va performance heuristic; paper co dong co ung dung ML, nhung phan note cho repo nen uu tien phan structural.
- Rat de nham cover-submodular-cost voi cover-modular-cost; day chinh la diem paper tong quat hoa.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: SCSC, SCSK, modular lower/upper bounds, ellipsoidal approximation cho submodular.
- Lemma co the tai su dung: surrogate bounds de chuyen bai toan submodular-submodular ve bai toan de hon.
- Technique lap lai: iterative surrogate optimization cho rang buoc submodular.
- Quan he voi nhom khac: no noi generalized cover co dien voi cac framework DS / constrained learning.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` o nhanh constrained / cover / knapsack generalization.
- `syntheses/dr-submodular.md` nen nhac paper nay nhu doi tac set-function de so sanh voi integer-lattice cover.
- `syntheses/k-submodular.md` khong can cap nhat truc tiep.
- `syntheses/mixed.md` co the them mot note ve "when both objective and constraints are submodular".

## Weaknesses / Limits

- Framework phuc tap, kho dong goi thanh mot theorem nho gon de nho.
- Rat phu thuoc vao chat luong cua surrogate; vi the proof sac hon truc giac algorithmic thuan tuy.

## Research Ideas Triggered

- Thu viet mot comparison note giua SCSC, generalized submodular cover, va DR-submodular cover.
- Xem co the dat mot taxonomy rieng cho "submodular objective + submodular constraint" thay vi gop chung vao cover khong.