# Metadata

- Title: Maximizing Approximately k-Submodular Functions
- Authors: Leqian Zheng, Hau Chan, Grigorios Loukides, Minming Li
- Year: 2021
- Venue: arXiv preprint (`arXiv:2101.07157v1`, January 18, 2021)
- Primary group: k-submodular
- Secondary tags: approximate-k-submodularity, noisy-objectives, total-size, individual-size, greedy, robustness
- Problem: maximizing functions that are only approximately k-submodular under total-size or individual-size constraints
- Main guarantee: introduces `eps`-approximately k-submodular and `eps`-approximately diminishing-returns notions, proves `eps`-ADR implies `eps`-AS, and derives greedy approximation ratios that degrade explicitly with `eps` and the size budgets
- Key techniques: multiplicative relaxation of k-submodularity, transfer lemmas from exact proxy functions, perturbation of greedy proofs for total-size and individual-size constraints, and sandwiching between exact and approximate objectives
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #approximate-k-submodularity #greedy #size-constraints #robustness #arXiv
- Inbox source: inbox/2101.07157v1.pdf