# Metadata

- Title: Maximizing k-Submodular Functions under Budget Constraint: Applications and Streaming Algorithms
- Authors: Canh V. Pham, Quang C. Vu, Dung K. T. Ha, Tai T. Nguyen, Nguyen D. Le
- Year: 2022
- Venue: Journal of Combinatorial Optimization; DOI 10.1007/s10878-022-00858-x
- Primary group: k-submodular
- Secondary tags: monotone, non-monotone, knapsack, streaming, total-budget, label-dependent-costs, journal-version
- Problem: budgeted k-submodular maximization under a single total budget, where each element may have either a common cost across labels or different costs `c_i(e)` depending on the assigned label
- Main guarantee: gives two single-pass streaming algorithms for budgeted k-submodular maximization; for the common-cost case a deterministic algorithm achieves `(1/4 - epsilon)` for monotone and `(1/5 - epsilon)` for non-monotone objectives, and for the general label-dependent-cost case a randomized algorithm achieves `min(alpha/2, (1-alpha)k / ((1+beta)k - beta)) - epsilon` for monotone and `min(alpha/2, (1-alpha)k / ((1+2beta)k - 2beta)) - epsilon` for non-monotone objectives in expectation
- Key techniques: opt-known threshold streaming template, geometric guessing of the optimum, marginal-per-cost thresholding, random label selection tuned to heterogeneous costs, best singleton fallback
- Status: processed-deep
- Tags: #k-submodular #budgeted #knapsack #streaming #non-monotone #label-dependent-costs
- Inbox source: inbox/Maximizing-k-submodular-functions-under-budget-constraint-applications-and-streaming-algorithms.pdf