We study the problem of maximizing a non-negative monotone submodular objective f subject to the intersection of k arbitrary matroid constraints. The natural greedy algorithm guarantees (k+1)-approximation for this problem, and the state-of-the-art algorithm only improves this approximation ratio to k. We give a (2k ln 2)/(1 + ln 2) + O(√k) < 0.819 k + O(√k) approximation algorithm for this problem. Our result is the first multiplicative improvement over the approximation ratio of the greedy algorithm for general k. We further show that our algorithm can be used to obtain roughly the same approximation ratio also for the more general problem in which the objective is not guaranteed to be monotone (the sublinear term in the approximation ratio becomes O(k^{2/3}) rather than O(√k) in this case). All of our results hold also when the k-matroid intersection constraint is replaced with a more general matroid k-parity constraint. Furthermore, unlike the case in many of the previous works, our algorithms run in time that is independent of k and polynomial in the size of the ground set. Our algorithms are based on a hybrid greedy local search approach recently introduced by Singer and Thiery [Neta Singer and Theophile Thiery, 2025] for the weighted matroid k-intersection problem, which is a special case of the problem we consider. Leveraging their approach in the submodular setting requires several non-trivial insights and algorithmic modifications since the marginals of a submodular function f, which correspond to the weights in the weighted case, are not independent of the algorithm’s internal randomness. In the special weighted case studied by [Neta Singer and Theophile Thiery, 2025], our algorithms reduce to a variant of the algorithm of [Neta Singer and Theophile Thiery, 2025] with an improved approximation ratio of (k + 1) ln 2 + O(ε) < 0.694k + 0.694 + O(ε), compared to an approximation ratio of (k+1)/(2ln 2) ≈ 0.722k + 0.722 guaranteed by Singer and Thiery [Neta Singer and Theophile Thiery, 2025].

We consider the weighted k-set packing problem, in which we are given a collection of weighted sets, each with at most k elements and must return a collection of pairwise disjoint sets with maximum total weight. For k = 3, this problem generalizes the classical 3-dimensional matching problem listed as one of the Karp's original 21 NP-complete problems. We give an algorithm attaining an approximation factor of 1.786 for 3-set packing, improving on the recent best result of due to Neuwohner.

Abstract. We consider the problem of optimizing a coverage function under an [Formula: see text]-matchoid of rank [Formula: see text]. We design fixed-parameter algorithms as well as streaming algorithms to compute an exact solution. Unlike previous work that presumes linear representativity of matroids, we consider the general oracle model. For the special case where the coverage function is linear, we give a deterministic fixed-parameter algorithm parameterized by [Formula: see text] and [Formula: see text]. This result, combined with the lower bounds of Lovasz [ Algebraic Methods in Graph Theory, Vol. II (Colloquium Szeged 1978 ), North-Holland, Amsterdam, 1981, pp. 495–517] and Jensen and Korte [ SIAM J. Comput., 11 (1982), pp. 184–190], demonstrates a separation between the [Formula: see text]-matchoid and the matroid [Formula: see text]-parity problems in the setting of fixed-parameter tractability. For a general coverage function, we give both deterministic and randomized fixed-parameter algorithms, parameterized by [Formula: see text] and [Formula: see text], where [Formula: see text] is the number of points covered in an optimal solution. The resulting algorithms can be directly translated into streaming algorithms. For unweighted coverage functions, we show that we can find an exact solution even when the function is given in the form of a value oracle (and so we do not have access to an explicit representation of the set system). Our result can be implemented in the streaming setting and stores a number of elements depending only on [Formula: see text] and [Formula: see text] but is completely independent of the total size [Formula: see text] of the ground set. This shows that it is possible to circumvent the recent space lower bound of Feldman et al. [ Proceedings of STOC, 2020, pp. 1363–1374] by parameterizing the solution value. This result, combined with existing lower bounds, also provides a new separation between the space and time complexity of maximizing an arbitrary submodular function and a coverage function in the value oracle model.

We study the following problem: Given a variable of interest, we would like to find a best linear predictor for it by choosing a subset of k relevant variables obeying a matroid constraint. This problem is a natural generalization of subset selection problems where it is necessary to spread observations amongst multiple different classes. We derive new, strengthened guarantees for this problem by improving the analysis of the residual random greedy algorithm and by developing a novel distorted local-search algorithm. To quantify our approximation guarantees, we refine the definition of weak submodularity by Das and Kempe (2011) and introduce the notion of an upper submodularity ratio, which we connect to the minimum k-sparse eigenvalue of the covariance matrix. More generally, we look at the problem of maximizing a set function f with lower and upper submodularity ratio $\gamma$ and $\beta$ under a matroid constraint. For this problem, our algorithms have asymptotic approximation guarantee 1/2 and (1 - 1/e) as the function is closer to being submodular. As a second application, we show that the Bayesian A-optimal design objective falls into our framework, leading to new guarantees for this problem as well.

We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general p-matchoid constraint in the model in which elements of the ground set arrive one at a time in a stream. The family of constraints we consider generalizes both the intersection of p arbitrary matroid constraints and p-uniform hypergraph matching. For monotone submodular functions, our algorithm attains a guarantee of p+1+ε using O(p/ε)-passes and requires storing only O(k) elements, where k is the maximum size of feasible solution. This immediately gives an O(1/ε)-pass (2+ε)-approximation for monotone submodular maximization in a matroid and (3+ε)-approximation for monotone submodular matching. Our algorithm is oblivious to the choice ε and can be stopped after any number of passes, delivering the appropriate guarantee. We extend our techniques to obtain the first multi-pass streaming algorithms for general, non-negative submodular functions subject to a p-matchoid constraint. We show that a randomized O(p/ε)-pass algorithm storing O(p³klog(k)/ε³) elements gives a (p+1+γ+O(ε))-approximation, where γ is the guarantee of the best-known offline algorithm for the same problem.

Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for $k$-means in Euclidean space with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of $9+\epsilon$, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of $k$-means and (2) satisfy the hard constraint that at most $k$ clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard linear programming (LP) relaxation. Our techniques are quite general, and we also show improved guarantees for $k$-median in Euclidean metrics and for a generalization of $k$-means in which the underlying metric is not required to be Euclidean.

It is generally believed that submodular functions–and the more general class of $\gamma$-weakly submodular functions–may only be optimized under the non-negativity assumption $f(S) \geq 0$. In this paper, we show that once the function is expressed as the difference $f = g - c$, where $g$ is monotone, non-negative, and $\gamma$-weakly submodular and $c$ is non-negative modular, then strong approximation guarantees may be obtained. We present an algorithm for maximizing $g - c$ under a $k$-cardinality constraint which produces a random feasible set $S$ such that $\mathbb{E}[g(S) -c(S)] \geq (1 - e^{-\gamma} - \epsilon) g(\opt) - c(\opt)$, whose running time is $O (\frac{n}{\epsilon} \log^2 \frac{1}{\epsilon})$, independent of $k$. We extend these results to the unconstrained setting by describing an algorithm with the same approximation guarantees and faster $O(n \frac{1}{\epsilon} \log\frac{1}{\epsilon})$ runtime. The main techniques underlying our algorithms are two-fold: the use of a surrogate objective which varies the relative importance between $g$ and $c$ throughout the algorithm, and a geometric sweep over possible $\gamma$ values. Our algorithmic guarantees are complemented by a hardness result showing that no polynomial-time algorithm which accesses $g$ through a value oracle can do better. We empirically demonstrate the success of our algorithms by applying them to experimental design on the Boston Housing dataset and directed vertex cover on the Email EU dataset.

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for k-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9 + ε, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) to satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of k-means where the underlying metric is not required to be Euclidean and for k-median in Euclidean metrics.

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee alpha(beta) depending on the number beta*k of clusters that may be opened. Our guarantee alpha(beta) is always at most 9 + epsilon and improves rapidly with beta (for example: alpha(2) < 2.59, and alpha(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. We develop a framework for bringing existing algorithms in the sequential setting to the distributed setting, achieving near optimal approximation ratios for many settings in only a constant number of MapReduce rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.

We consider the maximization problem in the value oracle model of functions defined on k -tuples of sets that are submodular in every orthant and r -wise monotone, where k ⩾ 2 and 1 ⩽ r ⩽ k . We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of 1/(1 + r ). For r = k , we give an analysis of a randomized greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+√ k /2. In the case of k = r = 2, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible both in the value query model and under the assumption that NP ≠ RP . Extending a result of Ando et al., we show that for any k ⩾ 3, submodularity in every orthant and pairwise monotonicity (i.e., r = 2) precisely characterize k -submodular functions. Consequently, we obtain an approximation guarantee of 1/3 (and thus independent of k ) for the maximization problem of k -submodular functions.

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We consider a distributed, greedy algorithm that combines previous approaches with randomization. The result is an algorithm that is embarrassingly parallel and achieves provable, constant factor, worst-case approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1 — c/e)-approximation — the first improvement over the greedy (1 — e−c)/c-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

Submodular functions play a key role in combinatorial optimization and in the study of valued constraint satisfaction problems. Recently, there has been interest in the class of bisubmodular functions, which assign values to disjoint pairs of sets. Like submodular functions, bisubmodular functions can be minimized exactly in polynomial time and exhibit the property of diminishing returns common to many problems in operations research. Recently, the class of k-submodular functions has been proposed. These functions generalize the notion of submodularity to k-tuples of sets, with submodular and bisubmodular functions corresponding to k = 1 and 2, respectively. In this paper, we consider the problem of maximizing bisubmodular and, more generally, k-submodular functions in the value oracle model. We provide the first approximation guarantees for maximizing a general bisubmodular or k-submodular function. We give an analysis of the naive random algorithm as well as a randomized greedy algorithm inspired by the recent randomized greedy algorithm of Buchbinder et al. [FOCS'12] for unconstrained submodular maximization. We show that this algorithm approximates any k-submodular function to a factor of . In the case of bisubmodular functions, our randomized greedy algorithm gives an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that NP ≠ RP. Our analysis provides further intuition for the algorithm of Buchbinder et al. [FOCS'12] in the submodular case. Additionally, we show that the naive random algorithm gives a 1/4-approximation for bisubmodular functions, corresponding again to known performance guarantees for submodular functions. Thus, bisubmodular functions exhibit approximability identical to submodular functions in all of the algorithmic contexts we consider.

In a stochastic probing problem we are given a universe E, where each element e in E is active independently with probability p in [0,1], and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements - if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented in [Gupta and Nagaraja, IPCO 2013], and provides a unified view of a number of problems. Thus far all the results in this general framework pertain only to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1-1/e)/(k_in+k_out+1)-approximation algorithm for the case in which we are given k_in greater than 0 matroids as inner constraints and k_out greater than 1 matroids as outer constraints. There are two main ingredients behind this result. First is a previously unpublished stronger bound on the continuous greedy algorithm due to Vondrak. Second is a rounding procedure that also allows us to obtain an improved 1/(k_in+k_out)-approximation for linear objective functions.

We present an optimal, combinatorial $1-1/e$ approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182--196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659--668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature $c$, we adapt our algorithm to produce a $(1-e^{-c})/c$ approximation. This matches results of Vondrák [STOC, ACM, New York, 2008, pp. 67--74], who has shown that the continuous greedy algorithm produces a $(1-e^{-c})/c$ approximation when the objective function has curvature $c$ with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model.

We present an optimal, combinatorial 1-1/e approximation algorithm for monotone sub modular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Calinescu, Chekuri, Pal and Vondrak, 2008), our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by local search. Both phases are run not on the actual objective function, but on a related non-oblivious potential function, which is also monotone sub modular. In our previous work on maximum coverage (Filmus and Ward, 2011), the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone sub modular functions. When the objective function is a coverage function, both definitions of the potential function coincide. The parameters used to define the potential function are closely related to Pade approximants of exp(x) evaluated at x = 1. We use this connection to determine the approximation ratio of the algorithm.

We present an optimal, combinatorial 1-1/e approximation algorithm for Maximum Coverage over a matroid constraint, using non-oblivious local search. Calinescu, Chekuri, Pál and Vondrák have given an optimal 1-1/e approximation algorithm for the more general problem of monotone submodular maximization over a matroid constraint. The advantage of our algorithm is that it is entirely combinatorial, and in many circumstances also faster, as well as conceptually simpler. Following previous work on satisfiability problems by Alimonti, as well as by Khanna, Motwani, Sudan and Vazirani, our local search algorithm is *non-oblivious*. That is, our algorithm uses an auxiliary linear objective function to evaluate solutions. This function gives more weight to elements covered multiple times. We show that the locality ratio of the resulting local search procedure is at least 1-1/e. Our local search procedure only considers improvements of size 1. In contrast, we show that oblivious local search, guided only by the problem's objective function, achieves an approximation ratio of only (n-1)/(2n-1-k) when improvements of size k are considered. In general, our local search algorithm could take an exponential amount of time to converge to an *exact* local optimum. We address this situation by using a combination of *approximate* local search and the same partial enumeration techniques as Calinescu et al., resulting in a clean 1 - 1/e-approximation algorithm running in polynomial time.

We consider the problem of maximizing a monotone submodular function in a $k$-exchange system. These systems, introduced by Feldman et al., generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. Feldman et al. show that a simple non-oblivious local search algorithm attains a $(k + 1)/2$ approximation ratio for the problem of linear maximization in a $k$-exchange system. Here, we extend this approach to the case of monotone submodular objective functions. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of $(k + 3)/2$ for the problem of maximizing a monotone submodular function in a $k$-exchange system.

Current formal software engineering methodologies provide a vast array of languages for specifying correctness properties, as well as a wide assortment automated tools that aid in the verification of specified properties. Unfortunately, the implementation of each such tool requires an early commitment to a particular methodology and language, in terms of both high-level semantic concerns and the lower-level syntactic representations of properties and proofs. In this paper, we present Prufrock, a novel approach to automated reasoning systems, which abstracts semantic concerns over entire classes of potential implementation languages. Prufrock utilizes polytypic programming techniques to create independent, reusable modules defining proof in different logics, independent of the language used to represent formulae in the logic, as well as the exact implementation of low-level prover functionality.