Moran Feldman

STOC Conference 2025 Conference Paper

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization

• Niv Buchbinder
• Moran Feldman

Maximization of submodular functions under various constraints is a fundamental problem that has been extensively studied. A powerful technique that has emerged and has been shown to be extremely effective for such problems is the following. First, a continuous relaxation of the problem is obtained by relaxing the (discrete) set of feasible solutions to a convex body, and extending the discrete submodular function f to a continuous function F known as the multilinear extension. Then, two algorithmic steps are implemented. The first step approximately solves the relaxation by finding a fractional solution within the convex body that approximately maximizes F ; and the second step rounds this fractional solution to a feasible integral solution. While this “fractionally solve and then round” approach has been a key technique for resolving many questions in the field, the main drawback of algorithms based on it is that evaluating the multilinear extension may require a number of value oracle queries to f that is exponential in the size of f ’s ground set. The only known way to tackle this issue is to approximate F via sampling, which makes all algorithms based on this approach inherently randomized and quite slow. In this work, we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful “solve fractionally and then round” approach. We demonstrate the effectiveness of this new tool on the fundamental problem of maximizing a submodular function subject to a matroid constraint, and show that it allows for a deterministic implementation of both the fractionally solving step and the rounding step of the above approach. As a bonus, we also get a randomized algorithm for the problem with an improved query complexity.

IJCAI Conference 2024 Conference Paper

Bridging the Gap between General and Down-Closed Convex Sets in Submodular Maximization

• Loay Mualem
• Murad Tukan
• Moran Feldman

Optimization of DR-submodular functions has experienced a notable surge in significance in recent times, marking a pivotal development within the domain of non-convex optimization. Motivated by real-world scenarios, some recent works have delved into the maximization of non-monotone DR-submodular functions over general (not necessarily down-closed) convex set constraints. Up to this point, these works have all used the minimum L-infinity norm of any feasible solution as a parameter. Unfortunately, a recent hardness result due to Mualem and Feldman shows that this approach cannot yield a smooth interpolation between down-closed and non-down-closed constraints. In this work, we suggest novel offline and online algorithms that provably provide such an interpolation based on a natural decomposition of the convex body constraint into two distinct convex bodies: a down-closed convex body and a general convex body. We also empirically demonstrate the superiority of our proposed algorithms across three offline and two online applications.

STOC Conference 2024 Conference Paper

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

• Niv Buchbinder
• Moran Feldman

Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late 1970’s. A central technique in this field is to approximately optimize the multilinear extension of the submodular objective, and then round the solution. The use of this technique requires a solver able to approximately maximize multilinear extensions. Following a long line of work, Buchbinder and Feldman (2019) described such a solver guaranteeing 0.385-approximation for down-closed constraints, while Oveis Gharan and Vondrák (2011) showed that no solver can guarantee better than 0.478-approximation. In this paper, we present a solver guaranteeing 0.401-approximation, which significantly reduces the gap between the best known solver and the inapproximability result. The design and analysis of our solver are based on a novel bound that we prove for DR-submodular functions. This bound improves over a previous bound due to Feldman et al. (2011) that is used by essentially all state-of-the-art results for constrained maximization of general submodular/DR-submodular functions. Hence, we believe that our new bound is likely to find many additional applications in related problems, and to be a key component for further improvement.

FOCS Conference 2024 Conference Paper

Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint

• Niv Buchbinder
• Moran Feldman

We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic non-oblivious local search algorithm that has an approximation guarantee of $1-1/e-\epsilon$ (for any $\epsilon > 0$ ) and query complexity of $\tilde{O}_{\epsilon}(nr)$, where $n$ is the size of the ground set and $r$ is the rank of the matroid. Our algorithm vastly improves over the previous state-of-the-art 0. 5008-approximation deterministic algorithm, and in fact, shows that there is no separation between the approximation guarantees that can be obtained by deterministic and randomized algorithms for the problem considered. The query complexity of our algorithm can be improved to $\tilde{O}_{\epsilon}(n+\hat{r}\sqrt{{n}})$ using randomization, which is nearly-linear for $r=O(\sqrt{n})$, and is always at least as good as the previous state-of-the-art algorithms.

NeurIPS Conference 2024 Conference Paper

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint

• Murad Tukan
• Loay Mualem
• Moran Feldman

Non-monotone constrained submodular maximization plays a crucial role in various machine learning applications. However, existing algorithms often struggle with a trade-off between approximation guarantees and practical efficiency. The current state-of-the-art is a recent $0. 401$-approximation algorithm, but its computational complexity makes it highly impractical. The best practical algorithms for the problem only guarantee $1/e$-approximation. In this work, we present a novel algorithm for submodular maximization subject to a cardinality constraint that combines a guarantee of $0. 385$-approximation with a low and practical query complexity of $O(n+k^2)$. Furthermore, we evaluate our algorithm's performance through extensive machine learning applications, including Movie Recommendation, Image Summarization, and more. These evaluations demonstrate the efficacy of our approach.

JMLR Journal 2023 Journal Article

How Do You Want Your Greedy: Simultaneous or Repeated?

• Moran Feldman
• Christopher Harshaw
• Amin Karbasi

We present SimulatneousGreedys, a deterministic algorithm for constrained submodular maximization. At a high level, the algorithm maintains $\ell$ solutions and greedily updates them in a simultaneous fashion. SimultaneousGreedys achieves the tightest known approximation guarantees for both $k$-extendible systems and the more general $k$-systems, which are $(k+1)^2/k = k + \mathcal{O}(1)$ and $(1 + \sqrt{k+2})^2 = k + \mathcal{O}(\sqrt{k})$, respectively. We also improve the analysis of RepeatedGreedy, showing that it achieves an approximation ratio of $k + \mathcal{O}(\sqrt{k})$ for $k$-systems when allowed to run for $\mathcal{O}(\sqrt{k})$ iterations, an improvement in both the runtime and approximation over previous analyses. We demonstrate that both algorithms may be modified to run in nearly linear time with an arbitrarily small loss in the approximation. Both SimultaneousGreedys and RepeatedGreedy are flexible enough to incorporate the intersection of $m$ additional knapsack constraints, while retaining similar approximation guarantees: both algorithms yield an approximation guarantee of roughly $k + 2m + \mathcal{O}(\sqrt{k+m})$ for $k$-systems and SimultaneousGreedys enjoys an improved approximation guarantee of $k+2m + \mathcal{O}(\sqrt{m})$ for $k$-extendible systems. To complement our algorithmic contributions, we prove that no algorithm making polynomially many oracle queries can achieve an approximation better than $k + 1/2 - \epsilon$. We also present SubmodularGreedy.jl, a Julia package which implements these algorithms. Finally, we test these algorithms on real datasets. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

NeurIPS Conference 2022 Conference Paper

Submodular Maximization in Clean Linear Time

• Wenxin Li
• Moran Feldman
• Ehsan Kazemi
• Amin Karbasi

In this paper, we provide the first deterministic algorithm that achieves $1/2$-approximation for monotone submodular maximization subject to a knapsack constraint, while making a number of queries that scales only linearly with the size of the ground set $n$. Moreover, our result automatically paves the way for developing a linear-time deterministic algorithm that achieves the tight $1-1/e$ approximation guarantee for monotone submodular maximization under a cardinality (size) constraint. To complement our positive results, we also show strong information-theoretic lower bounds. More specifically, we show that when the maximum cardinality allowed for a solution is constant, no deterministic or randomized algorithm making a sub-linear number of function evaluations can guarantee any constant approximation ratio. Furthermore, when the constraint allows the selection of a constant fraction of the ground set, we show that any algorithm making fewer than $\Omega(n/\log(n))$ function evaluations cannot perform better than an algorithm that simply outputs a uniformly random subset of the ground set of the right size. We extend our results to the general case of maximizing a monotone submodular function subject to the intersection of a $p$-set system and multiple knapsack constraints. Finally, we evaluate the performance of our algorithms on multiple real-life applications, including movie recommendation, location summarization, Twitter text summarization, and video summarization.

NeurIPS Conference 2022 Conference Paper

Using Partial Monotonicity in Submodular Maximization

• Loay Mualem
• Moran Feldman

Over the last two decades, submodular function maximization has been the workhorse of many discrete optimization problems in machine learning applications. Traditionally, the study of submodular functions was based on binary function properties, but recent works began to consider continuous function properties such as the submodularity ratio and the curvature. The monotonicity property of set functions plays a central role in submodular maximization. Nevertheless, no continuous version of this property has been suggested to date (as far as we know), which is unfortunate since submoduar functions that are almost monotone often arise in machine learning applications. In this work we fill this gap by defining the monotonicity ratio, which is a continuous version of the monotonicity property. We then show that for many standard submodular maximization algorithms one can prove new approximation guarantees that depend on the monotonicity ratio; leading to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming, image summarization and ride-share optimization.

ICML Conference 2021 Conference Paper

Regularized Submodular Maximization at Scale

• Ehsan Kazemi 0001
• Shervin Minaee
• Moran Feldman
• Amin Karbasi

In this paper, we propose scalable methods for maximizing a regularized submodular function $f \triangleq g-\ell$ expressed as the difference between a monotone submodular function $g$ and a modular function $\ell$. Submodularity is inherently related to the notions of diversity, coverage, and representativeness. In particular, finding the mode (i. e. , the most likely configuration) of many popular probabilistic models of diversity, such as determinantal point processes and strongly log-concave distributions, involves maximization of (regularized) submodular functions. Since a regularized function $f$ can potentially take on negative values, the classic theory of submodular maximization, which heavily relies on the non-negativity assumption of submodular functions, is not applicable. To circumvent this challenge, we develop the first one-pass streaming algorithm for maximizing a regularized submodular function subject to a $k$-cardinality constraint. Furthermore, we develop the first distributed algorithm that returns a solution $S$ in $O(1/ \epsilon)$ rounds of MapReduce computation. We highlight that our result, even for the unregularized case where the modular term $\ell$ is zero, improves the memory and communication complexity of the state-of-the-art by a factor of $O(1/ \epsilon)$ while arguably provides a simpler distributed algorithm and a unifying analysis. We empirically study the performance of our scalable methods on a set of real-life applications, including finding the mode of negatively correlated distributions, vertex cover of social networks, and several data summarization tasks.

NeurIPS Conference 2021 Conference Paper

Submodular + Concave

• Siddharth Mitra
• Moran Feldman
• Amin Karbasi

It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for (non-convex/non-concave) continuous submodular functions. In this work, we initiate the study of the maximization of functions of the form $F(x) = G(x) +C(x)$ over a solvable convex body $P$, where $G$ is a smooth DR-submodular function and $C$ is a smooth concave function. This class of functions is a strict extension of both concave and continuous DR-submodular functions for which no theoretical guarantee is known. We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i. e. , if $G$ and $C$ are monotone or not, and non-negative or not) and on the nature of the set $P$ (i. e. , whether it is downward closed or not), provide $1-1/e$, $1/e$, or $1/2$ approximation guarantees. We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines.

NeurIPS Conference 2020 Conference Paper

Continuous Submodular Maximization: Beyond DR-Submodularity

• Moran Feldman
• Amin Karbasi

In this paper, we propose the first continuous optimization algorithms that achieve a constant factor approximation guarantee for the problem of monotone continuous submodular maximization subject to a linear constraint. We first prove that a simple variant of the vanilla coordinate ascent, called \COORDINATE-ASCENT+, achieves a $(\frac{e-1}{2e-1}-\eps)$-approximation guarantee while performing $O(n/\epsilon)$ iterations, where the computational complexity of each iteration is roughly $O(n/\sqrt{\epsilon}+n\log n)$ (here, $n$ denotes the dimension of the optimization problem). We then propose \COORDINATE-ASCENT++, that achieves the tight $(1-1/e-\eps)$-approximation guarantee while performing the same number of iterations, but at a higher computational complexity of roughly $O(n^3/\eps^{2. 5} + n^3 \log n / \eps^2)$ per iteration. However, the computation of each round of \COORDINATE-ASCENT++ can be easily parallelized so that the computational cost per machine scales as $O(n/\sqrt{\epsilon}+n\log n)$.

ICML Conference 2020 Conference Paper

Streaming Submodular Maximization under a k-Set System Constraint

• Ran Haba
• Ehsan Kazemi 0001
• Moran Feldman
• Amin Karbasi

In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the currently tightest deterministic approximation ratio for submodular maximization subject to a $k$-matchoid constraint. Moreover, we propose the first streaming algorithm for monotone submodular maximization subject to $k$-extendible and $k$-set system constraints. Together with our proposed reduction, we obtain $O(k\log k)$ and $O(k^2\log k)$ approximation ratio for submodular maximization subject to the above constraints, respectively. We extensively evaluate the empirical performance of our algorithm against the existing work in a series of experiments including finding the maximum independent set in randomly generated graphs, maximizing linear functions over social networks, movie recommendation, Yelp location summarization, and Twitter data summarization.

STOC Conference 2020 Conference Paper

The one-way communication complexity of submodular maximization with applications to streaming and robustness

• Moran Feldman
• Ashkan Norouzi-Fard
• Ola Svensson
• Rico Zenklusen

NeurIPS Conference 2019 Conference Paper

Adaptive Sequence Submodularity

• Marko Mitrovic
• Ehsan Kazemi
• Moran Feldman
• Andreas Krause
• Amin Karbasi

In many machine learning applications, one needs to interactively select a sequence of items (e. g. , recommending movies based on a user's feedback) or make sequential decisions in a certain order (e. g. , guiding an agent through a series of states). Not only do sequences already pose a dauntingly large search space, but we must also take into account past observations, as well as the uncertainty of future outcomes. Without further structure, finding an optimal sequence is notoriously challenging, if not completely intractable. In this paper, we view the problem of adaptive and sequential decision making through the lens of submodularity and propose an adaptive greedy policy with strong theoretical guarantees. Additionally, to demonstrate the practical utility of our results, we run experiments on Amazon product recommendation and Wikipedia link prediction tasks.

SODA Conference 2019 Conference Paper

Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid

• Niv Buchbinder
• Moran Feldman
• Mohit Garg 0003

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (½ + ε )-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the ½-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.

ICML Conference 2019 Conference Paper

Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications

• Chris Harshaw
• Moran Feldman
• Justin Ward
• Amin Karbasi

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.

STOC Conference 2019 Conference Paper

Unconstrained submodular maximization with constant adaptive complexity

• Lin Chen 0003
• Moran Feldman
• Amin Karbasi

SODA Conference 2018 Conference Paper

A Framework for the Secretary Problem on the Intersection of Matroids

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.

NeurIPS Conference 2018 Conference Paper

Do Less, Get More: Streaming Submodular Maximization with Subsampling

• Moran Feldman
• Amin Karbasi
• Ehsan Kazemi

In this paper, we develop the first one-pass streaming algorithm for submodular maximization that does not evaluate the entire stream even once. By carefully subsampling each element of the data stream, our algorithm enjoys the tightest approximation guarantees in various settings while having the smallest memory footprint and requiring the lowest number of function evaluations. More specifically, for a monotone submodular function and a $p$-matchoid constraint, our randomized algorithm achieves a $4p$ approximation ratio (in expectation) with $O(k)$ memory and $O(km/p)$ queries per element ($k$ is the size of the largest feasible solution and $m$ is the number of matroids used to define the constraint). For the non-monotone case, our approximation ratio increases only slightly to $4p+2-o(1)$. To the best or our knowledge, our algorithm is the first that combines the benefits of streaming and subsampling in a novel way in order to truly scale submodular maximization to massive machine learning problems. To showcase its practicality, we empirically evaluated the performance of our algorithm on a video summarization application and observed that it outperforms the state-of-the-art algorithm by up to fifty-fold while maintaining practically the same utility. We also evaluated the scalability of our algorithm on a large dataset of Uber pick up locations.

ICML Conference 2018 Conference Paper

Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?

• Lin Chen 0003
• Moran Feldman
• Amin Karbasi

Submodular functions are a broad class of set functions that naturally arise in many machine learning applications. Due to their combinatorial structures, there has been a myriad of algorithms for maximizing such functions under various constraints. Unfortunately, once a function deviates from submodularity (even slightly), the known algorithms may perform arbitrarily poorly. Amending this issue, by obtaining approximation results for functions obeying properties that generalize submodularity, has been the focus of several recent works. One such class, known as weakly submodular functions, has received a lot of recent attention from the machine learning community due to its strong connections to restricted strong convexity and sparse reconstruction. In this paper, we prove that a randomized version of the greedy algorithm achieves an approximation ratio of $(1 + 1/\gamma )^{-2}$ for weakly submodular maximization subject to a general matroid constraint, where $\gamma$ is a parameter measuring the distance from submodularity. To the best of our knowledge, this is the first algorithm with a non-trivial approximation guarantee for this constrained optimization problem. Moreover, our experimental results show that our proposed algorithm performs well in a variety of real-world problems, including regression, video summarization, splice site detection, and black-box interpretation.

SODA Conference 2017 Conference Paper

Building a Good Team: Secretary Problems and the Supermodular Degree

• Moran Feldman
• Rani Izsak

SODA Conference 2017 Conference Paper

O (depth)-Competitive Algorithm for Online Multi-level Aggregation

• Niv Buchbinder
• Moran Feldman
• Joseph Naor
• Ohad Talmon

We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. [7]. In this problem requests arrive over time at the nodes of the tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply- chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online O (D)-competitive algorithm for the problem, where D is the depth, or number of levels, of the aggregation tree. This result improves upon the D 2 2 d - competitive algorithm obtained recently by Bienkowski et al. [7].

NeurIPS Conference 2017 Conference Paper

Streaming Weak Submodularity: Interpreting Neural Networks on the Fly

• Ethan Elenberg
• Alexandros Dimakis
• Moran Feldman
• Amin Karbasi

In many machine learning applications, it is important to explain the predictions of a black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a combinatorial maximization problem and propose an efficient streaming algorithm to solve it subject to cardinality constraints. By extending ideas from Badanidiyuru et al. [2014], we provide a constant factor approximation guarantee for our algorithm in the case of random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions 10 times faster than the state-of-the-art LIME framework of Ribeiro et al. [2016].

SODA Conference 2016 Conference Paper

Deterministic Algorithms for Submodular Maximization Problems

• Niv Buchbinder
• Moran Feldman

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

SODA Conference 2016 Conference Paper

Online Contention Resolution Schemes

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.

SODA Conference 2015 Conference Paper

A Simple O (log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

Only recently progress has been made in obtaining o (log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a -competitive procedure, and Lachish (2014) recently presented a O (log log(rank))-competitive algorithm. Both algorithms are involved with complex analyses. Using different tools, we present a considerably simpler O (log log(rank))-competitive algorithm. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. We are also able to vastly improve on the hidden constant in the competitive ratio.

SODA Conference 2015 Conference Paper

Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization

• Niv Buchbinder
• Moran Feldman
• Roy Schwartz 0002

Fast algorithms for submodular maximization problems have a vast potential use in applicative settings, such as machine learning, social networks, and economics. Though fast algorithms were known for some special cases, only recently Badanidiyuru and Vondrák [4] were the first to explicitly look for such algorithms in the general case of maximizing a monotone submodular function subject to a matroid independence constraint. The algorithm of Badanidiyuru and Vondrák matches the best possible approximation guarantee, while trying to reduce the number of value oracle queries the algorithm performs. Our main result is a new algorithm for this general case which establishes a surprising tradeoff between two seemingly unrelated quantities: the number of value oracle queries and the number of matroid independence queries performed by the algorithm. Specifically, one can decrease the former by increasing the latter and vice versa, while maintaining the best possible approximation guarantee. Such a tradeoff is very useful since various applications might incur significantly different costs in querying the value and matroid independence oracles. Furthermore, in case the rank of the matroid is O ( n c ), where n is the size of the ground set and c is an absolute constant smaller than 1, the total number of oracle queries our algorithm uses can be made to have a smaller magnitude compared to that needed by [4]. We also provide even faster algorithms for the well studied special cases of a cardinality constraint and a partition matroid independence constraint, both of which capture many real-world applications and have been widely studied both theorically and in practice.

SODA Conference 2015 Conference Paper

Online Submodular Maximization with Preemption

• Niv Buchbinder
• Moran Feldman
• Roy Schwartz 0002

Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one-by-one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is to maximize a submodular function over the set of elements in the solution. We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a 1/ e -competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most k elements in its solution.

FOCS Conference 2015 Conference Paper

The Submodular Secretary Problem Goes Linear

• Moran Feldman
• Rico Zenklusen

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The interest in MSP is twofold: on the one hand, there are many interesting applications of MSP, and on the other hand, there is strong hope that MSP admits O(1)-competitive algorithms, which is the claim of the well-known matroid secretary conjecture. Partially linked to its numerous applications in mechanism design, substantial interest arose also in the study of nonlinear versions of MSP, with a focus on the sub modular matroid secretary problem (SMSP). The fact that sub modularity captures the property of diminishing returns, a very natural property for valuation functions, is a key reason for the interest in SMSP. So far, O(1)-competitive algorithms have been obtained for SMSP over some basic matroid classes. This created some hope that, analogously to the matroid secretary conjecture, one may even obtain O(1)-competitive algorithms for SMSP over any matroid. However, up to now, most questions related to SMSP remained open, including whether SMSP may be substantially more difficult than MSP, and more generally, to what extend MSP and SMSP are related. Our goal is to address these points by presenting general black-box reductions from SMSP to MSP. In particular, we show that any O(1)-competitive algorithm for MSP, even restricted to a particular matroid class, can be transformed in a black-box way to an O(1)-competitive algorithm for SMSP over the same matroid class. This implies that the matroid secretary conjecture is equivalent to the same conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP. Also, to find O(1)-competitive algorithms for SMSP over a particular matroid class, it suffices to consider MSP over the same matroid class. Using our reductions we obtain many first and improved O(1)-competitive algorithms for SMSP over various matroid classes by leveraging known algorithms for MSP. Moreover, our reductions imply an O(log log(rank))-competitive algorithm for SMSP, thus, matching the currently best asymptotic algorithm for MSP, and substantially improving on the previously best O(log(rank))-competitive algorithm for SMSP.

SODA Conference 2014 Conference Paper

Submodular Maximization with Cardinality Constraints

• Niv Buchbinder
• Moran Feldman
• Joseph Naor
• Roy Schwartz 0002

We consider the problem of maximizing a (non-monotone) submodular function subject to a cardinality constraint. In addition to capturing well-known combinatorial optimization problems, e. g. , Max- k -Coverage and Max-Bisection, this problem has applications in other more practical settings such as natural language processing, information retrieval, and machine learning. In this work we present improved approximations for two variants of the cardinality constraint for non-monotone functions. When at most k elements can be chosen, we improve the current best approximation to a factor that is in the range [ ], achieving a tight approximation of for and breaking the barrier for all values of k. When exactly k elements must be chosen, our algorithms improve the current best approximation to a factor that is in the range [0. 356, ], again achieving a tight approximation of for. Additionally, some of the algorithms we provide are very fast with time complexities of O ( nk ), as opposed to previous known algorithms which are continuous in nature, and thus, too slow for applications in the practical settings mentioned above. Our algorithms are based on two new techniques. First, we present a simple randomized greedy approach where in each step a random element is chosen from a set of “reasonably good” elements. This approach might be considered a natural substitute for the greedy algorithm of Nemhauser, Wolsey and Fisher [45], as it retains the same tight guarantee of for monotone objectives and the same time complexity of O ( nk ), while giving an approximation of for general non-monotone objectives (while the greedy algorithm of Nemhauser et. al. fails to provide any constant guarantee). Second, we extend the double greedy technique, which achieves a tight approximation for unconstrained submodular maximization, to the continuous setting. This allows us to manipulate the natural rates by which elements change, thus bounding the total number of elements chosen.

FOCS Conference 2012 Conference Paper

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

• Niv Buchbinder
• Moran Feldman
• Joseph Naor
• Roy Schwartz 0002

We consider the Unconstrained Submodular Maximization problem in which we are given a non-negative submodular function f: 2 N → ℝ +, and the objective is to find a subset S ⊆ N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well known problems captured by Unconstrained Submodular Maximization include MaxCut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige et al. [11]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. Our method might seem counterintuitive, since it is known that the greedy algorithm fails to achieve any bounded approximation factor for the problem.

FOCS Conference 2011 Conference Paper

A Unified Continuous Greedy Algorithm for Submodular Maximization

• Moran Feldman
• Joseph Naor
• Roy Schwartz 0002

The study of combinatorial problems with a submodular objective function has attracted much attention in recent years, and is partly motivated by the importance of such problems to economics, algorithmic game theory and combinatorial optimization. Classical works on these problems are mostly combinatorial in nature. Recently, however, many results based on continuous algorithmic tools have emerged. The main bottleneck of such continuous techniques is how to approximately solve a non-convex relaxation for the sub- modular problem at hand. Thus, the efficient computation of better fractional solutions immediately implies improved approximations for numerous applications. A simple and elegant method, called "continuous greedy", successfully tackles this issue for monotone submodular objective functions, however, only much more complex tools are known to work for general non-monotone submodular objectives. In this work we present a new unified continuous greedy algorithm which finds approximate fractional solutions for both the non-monotone and monotone cases, and improves on the approximation ratio for many applications. For general non-monotone submodular objective functions, our algorithm achieves an improved approximation ratio of about 1/e. For monotone submodular objective functions, our algorithm achieves an approximation ratio that depends on the density of the polytope defined by the problem at hand, which is always at least as good as the previously known best approximation ratio of 1-1/e. Some notable immediate implications are an improved 1/e-approximation for maximizing a non-monotone submodular function subject to a matroid or O(1)-knapsack constraints, and information-theoretic tight approximations for Submodular Max-SAT and Submodular Welfare with k players, for any number of players k. A framework for submodular optimization problems, called the contention resolution framework, was introduced recently by Chekuri et al. [11]. The improved approximation ratio of the unified continuous greedy algorithm implies improved ap- proximation ratios for many problems through this framework. Moreover, via a parameter called stopping time, our algorithm merges the relaxation solving and re-normalization steps of the framework, and achieves, for some applications, further improvements. We also describe new monotone balanced con- tention resolution schemes for various matching, scheduling and packing problems, thus, improving the approximations achieved for these problems via the framework.

SODA Conference 2009 Conference Paper

Improved approximating algorithms for Directed Steiner Forest

• Moran Feldman
• Guy Kortsarz
• Zeev Nutov