# Metadata

- Title: Submodular Maximization in Exactly n Queries
- Authors: Eric Balkanski, Steven DiSilvio, Alan Kuhnle, ChunLi Peng
- Year: 2024
- Venue: arXiv preprint
- Primary group: submodular
- Secondary tags: matroid, p-matchoid, linear-query, deterministic, non-monotone, query-complexity
- Problem: deterministic submodular maximization under matroid and p-matchoid constraints with oracle-query complexity as the main efficiency metric
- Main guarantee: gives a deterministic `1/4`-approximation for monotone matroid-constrained maximization in exactly `n` value queries, a deterministic `1/(6 + 4 sqrt(2))`-approximation for general submodular matroid-constrained maximization in exactly `2n` queries, and a deterministic `1/(4p)`-approximation for monotone p-matchoid maximization in exactly `n` queries
- Key techniques: querying infeasible supersets, fixed arrival-time marginal weights, exchange graphs and injections, two-disjoint-copy reduction for the non-monotone case, p-matchoid exchange candidates without re-querying
- Status: processed-deep
- Tags: #submodular #matroid #p-matchoid #linear-query #deterministic #non-monotone
- Inbox source: inbox/2406.00148v2.pdf