# Can sampling remove the limitations in greedy algorithm?

Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of greedy algorithm?

I understand the answer to this is problem-specific, but given a problem that shows the limitation of greedy algorithm can sampling be used in any way in order to guide the greedy algorithm to generate an optimal solution?

• Crossposted on cstheory.se: cstheory.stackexchange.com/questions/30813/…. – Yuval Filmus Mar 15 '15 at 1:59
• Intuitively speaking, sampling can't always help. One case where greedy algorithms fail is if there are a very small number of optimal solutions and they're hard to find. But if the number of optimal solutions is small, sampling is unlikely to help you find one. – David Richerby Mar 15 '15 at 11:18
• You should buy a new keyboard with capital letters included. It would improve your contributions. – babou Mar 15 '15 at 18:47
• Greedy algorithms sometimes find optimal solutions, sometimes they don't. What kind of sampling do you mean? How can randomization ever move an algorithm from non-optimality to optimality (as in, always finding an optimal solution)? – Raphael Mar 15 '15 at 20:02
• Please don't cross-post on multiple SE sites (e.g., CS.SE and CSTheory.SE). That violates site rules, and it is impolite as it fragments discussion and answers. – D.W. Mar 16 '15 at 1:45

Positive answer. Consider the problem of maximizing a non-negative submodular function under a cardinality constraint. In this problem, you are given a submodular function $f$ over a domain $U$, and a bound $k$. Your task is to find a subset $S \subset U$ of size at most $k$ such that $f(S)$ is as large as possible. This problem is hard (more on that below), and so we make do with approximation algorithms. The greedy algorithm has no guarantees in this regard, but a simple modification of it gives a (probably non-optimal) $1/e$ guarantee. See Buchbinder–Feldman–Naor–Schwartz.
Negative answer. In what sense is the problem of maximizing a non-negative submodular function under a cardinality constraint hard? One such sense is hardness in the value oracle model. Suppose that an approximation algorithm is given oracle access to the function $f$. Then if $f$ always produces a $1/2+\epsilon$ approximation, there must be some $f$ and $k$ for which it calls the oracle exponentially many times (in $n = |U|$), a result due to Vondrák. This hardness result holds even for randomized algorithms (with any constant success probability). So randomization has its limits as an ingredient.
Does randomness help? Take the closely related problem of unconstrained submodular maximization – the case $k = n$ (recall $n = |U|$) of the problem considered above. The algorithm of Buchbinder–Feldman–Naor–Schwartz yields the optimal 1/2 approximation, but is randomized. They also give a 1/3 approximation algorithm which is deterministic, matching previous guarantees of Feige–Mirrokni–Vondrák. Can deterministic algorithms achieve the randomized guarantee? (Rumour has it that the answer is: Yes.)