# Guess Free Maximization of Submodular and Linear Sums

arXiv: https://arxiv.org/abs/1810.03813 · HTML: https://mlsanity.com/paper/1810.03813/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2018.

## Built on by (most cited first, 13 of 13)

- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions](https://mlsanity.com/paper/2101.01631/) (2021)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees](https://mlsanity.com/paper/2608.19993/) (2026)
- [Submodular Optimization Beyond Nonnegativity: Adaptive Seed Selection in Incentivized Social Advertising](https://mlsanity.com/paper/2109.15180/) (2021)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)
- [No-Regret Online Prediction with Strategic Experts](https://mlsanity.com/paper/2305.15331/) (2023)
- [A QUBO Framework for Team Formation](https://mlsanity.com/paper/2503.23209/) (2025)

## Abstract (arXiv)

We consider the problem of maximizing the sum of a monotone submodular function and a linear function subject to a general solvable polytope constraint. Recently, Sviridenko et al. (2017) described an algorithm for this problem whose approximation guarantee is optimal in some intuitive and formal senses. Unfortunately, this algorithm involves a guessing step which makes it less clean and significantly affects its time complexity. In this work we describe a clean alternative algorithm that uses a novel weighting technique in order to avoid the problematic guessing step while keeping the same approximation guarantee as the algorithm of Sviridenko et al.