## Submodular maximization and its generalization through an intersection cut lens

 We study a mixed-integer set $$\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}$$ arising in the submodular maximization problem, where $$f$$ is a submodular function defined over $$\{0,1\}^n$$. We use intersection cuts to tighten a polyhedral outer approximation of $$\mathcal{S}$$. We construct a continuous extension $$\mathsf{F}$$ of $$f$$, which is convex and defined over … Read more

## Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function … Read more

## Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more