Submodular function maximization has found a wealth of new applications in recent years. The related supermodular maximization models also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints. Hence, while there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems.

Contention resolution schemes (or CR schemes), introduced by Chekuri, Vondrak and Zenklusen, are a class of randomized rounding algorithms for converting a fractional solution to a relaxation for a down-closed constraint family into an integer solution. A CR scheme takes a fractional point x in a relaxation polytope, rounds each coordinate xi independently to get a possibly non-feasible set, and then drops some elements in order to satisfy the constraints. Intuitively, a CR scheme is c-balanced if every element i is selected with probability at least c⋅xi. It is known that general matroids admit a (1−1/e)-balanced CR scheme, and that this is (asymptotically) optimal. This is in particular true for the special case of uniform matroids of rank one. In this work, we provide a simple and explicit monotone CR scheme for uniform matroids of rank k on n elements with a balancedness of 1−(nk)(1−kn)n+1−k(kn)k, and show that this is optimal. As n grows, this expression converges from above to 1−e−kkk/k!. While this asymptotic bound can be obtained by combining previously known results, these require defining an exponential-sized linear program, as well as using random sampling and the ellipsoid algorithm. Our procedure, on the other hand, has the advantage of being simple and explicit. This scheme extends naturally into an optimal CR scheme for partition matroids.

A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{cT x: Tx ≤ b, γT x ≡ r (mod m), x ∊ ℤn} with a totally unimodular constraint matrix T. Such problems have been shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i.e., full-rank matrices whose n × n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., for m > 2. We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3. Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems, and deducing bounds on the proximity between solutions of the problem and its relaxation.

The multilinear framework was developed to achieve the breakthrough 1 – 1/e approximation for maximizing a monotone submodular function subject to a matroid constraint, which includes the submodular welfare problem as special case. This framework has a continuous optimization part (solving the multilinear extension of a submodular set function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts so that the resulting generalized framework may be used on a wider array of problems. In particular, we make a conceptual contribution by identifying a family of parameterized functions and their applications. As a running example we focus on solving diversity problems max , where ℳ is matroid. These diversity functions have Aij ≥ 0 as a measure of dissimilarity of i, j, and A has 0-diagonal. This family of problems ranges from intractable problems such as densest k-subgraph, to ½-approximable metric diversity problems. The multilinear extension F of such diversity functions satisfies ▿2F(x) = A ≥ 0 and hence the original multilinear framework (which assumes non-positive Hessians) does not directly apply. Instead we introduce a new parameter for functions F ∊ C2 which measures the approximability of the associated problem max{F(x) : x ∊ P}, for solvable downwards-closed polytopes P. A function F is called one-sided σ-smooth if for all u, x ≥ 0, x = 0. For σ = 0 this class includes previously studied classes such as continuous DR-submodular functions, and much more. For the multlinear extension of a diversity function, we show that it is one-sided σ-smooth whenever Aij forms a σ-semi-metric. We give an Ω(1/σ)-approximation for the continuous maximization problem of monotone, normalized one-sided σ-smooth F with an additional property: non-positive third order partial derivatives. Since the multilinear extension of a diversity function has this additional property we can apply the extended multilinear framework to this family of discrete problems. This requires new matroid rounding techniques for quadratic objectives. The result is an Ω(1/σ3/2)-approximation for maximizing a σ-semi-metric diversity function subject to matroid constraint. This improves upon the previous best bound of Ω(1/σ) and we give evidence that it may be tight. For general one-sided smooth functions, we show the continuous process gives an Ω(1/32σ)-approximation, independent of n. In this setting, by discretizing, we present a concrete poly-time algorithm for multilinear functions that satisfy the one-sided σ-smoothness condition.

Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.

Submodular functions have found a wealth of new applications in data science and machine learning models in recent years. This has been coupled with many algorithmic advances in the area of submodular optimization: (SO) $\min/\max f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow \mathbb{R}$ is submodular. In this work we focus on a more general class of multivariate submodular optimization (MVSO) problems: $\min/\max f (S_1,S_2,\ldots,S_k): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote union of disjoint sets and hence this model is attractive where resources are being allocated across $k$ agents, who share a “joint” multivariate nonnegative objective $f(S_1,S_2,\ldots,S_k)$ that captures some type of submodularity (i.e. diminishing returns) property. We provide some explicit examples and potential applications for this new framework. For maximization, we show that practical algorithms such as accelerated greedy variants and distributed algorithms achieve good approximation guarantees for very general families (such as matroids and $p$-systems). For arbitrary families, we show that monotone (resp. nonmonotone) MVSO admits an $\alpha (1-1/e)$ (resp. $\alpha \cdot 0.385$) approximation whenever monotone (resp. nonmonotone) SO admits an $\alpha$-approximation over the multilinear formulation. This substantially expands the family of tractable models. On the minimization side we give essentially optimal approximations in terms of the curvature of $f$.

Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) $\min/\max~f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow \mathbb{R}$ is submodular. This progress has been coupled with a wealth of new applications for these models. Our focus is on a more general class of \emph{multi-agent submodular optimization} (MASO) which was introduced by Goel et al. in the minimization setting: $\min \sum_i f_i(S_i): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote disjoint union and hence this model is attractive where resources are being allocated across $k$ agents, each with its own submodular cost function $f_i()$. In this paper we explore the extent to which the approximability of the multi-agent problems are linked to their single-agent {\em primitives}, referred to informally as the {\em multi-agent gap}. We present different reductions that transform a multi-agent problem into a single-agent one. For maximization we show that (MASO) admits an $O(α)$-approximation whenever (SO) admits an $α$-approximation over the multilinear formulation, and thus substantially expanding the family of tractable models. We also discuss several family classes (such as spanning trees, matroids, and $p$-systems) that have a provable multi-agent gap of 1. In the minimization setting we show that (MASO) has an $O(α\cdot \min \{k, \log^2 (n)\})$-approximation whenever (SO) admits an $α$-approximation over the convex formulation. In addition, we discuss the class of "bounded blocker" families where there is a provably tight O$(\log n)$ gap between (MASO) and (SO).