1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Crossposted on cstheory.se: cstheory.stackexchange.com/questions/30813/…. $\endgroup$ – Yuval Filmus Mar 15 '15 at 1:59
  • $\begingroup$ 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. $\endgroup$ – David Richerby Mar 15 '15 at 11:18
  • $\begingroup$ You should buy a new keyboard with capital letters included. It would improve your contributions. $\endgroup$ – babou Mar 15 '15 at 18:47
  • $\begingroup$ 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)? $\endgroup$ – Raphael Mar 15 '15 at 20:02
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 16 '15 at 1:45
6
$\begingroup$

It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic algorithms) being only one of them. That said, I have a positive answer and a negative answer for you.

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.)

Can randomization help? Under the widely held belief that P=BPP, there cannot be any discrepancy between randomized and deterministic polytime algorithms. However, this holds only in the model in which the input is given explicitly. In the value oracle model, the input is given implicitly as an oracle, and so it could be that randomized algorithms outperform deterministic ones. Indeed, it is easy to come up with specific tasks which are much easier for randomized algorithms. The question is whether unconstrained submodular maximization is one of these examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.