# Metadata

- Title: Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints
- Authors: Akbar Rafiey, Yuichi Yoshida
- Year: 2020
- Venue: arXiv preprint (`arXiv:2006.15744v1`, June 29, 2020)
- Primary group: k-submodular
- Secondary tags: differential-privacy, matroid, monotone, multilinear-extension, exponential-mechanism, query-efficiency, submodular
- Problem: differentially private maximization of low-sensitivity monotone submodular and monotone k-submodular functions subject to a matroid constraint
- Main guarantee: gives a private `(1 - 1 / e)` approximation for monotone submodular matroid maximization and the first private `1 / 2` approximation for monotone k-submodular matroid maximization, both with additive sensitivity-dependent loss and faster sampled variants
- Key techniques: private continuous greedy over a discretized matroid polytope, exponential mechanism, privacy composition, sampled candidate reduction, and privatized greedy assignment for k-submodular functions
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #submodular #differential-privacy #matroid #monotone #multilinear-extension #approximation #arXiv
- Inbox source: inbox/2006.15744v1.pdf