- Dynamic Programming
- The Greedy-Strategy
- Divide-and-Conquer
While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C. Firstly, I am aware of something that we (or rather, the prof) introduced in a functional programming class, called an “algorithmic skeleton”, that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows: Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems. Then, a D&C-skeleton is a 4-tuple $(P_beta, beta, mathcal{D}, mathcal{C})$, where:
- $P_beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_beta(p)$ holds.
- $beta$ is a mapping $P_beta rightarrow S$ that assigns a solution to each basic problem.
- $mathcal{D}$ is a mapping $P rightarrow mathfrak{P}(P)$ that divides each problem into a set of subproblems.
- $mathcal{C}$ is a mapping $Ptimes mathfrak{P}(S) rightarrow S$ that joins the solutions (depending on kind of a “pivot problem”) of the subproblems to produce a solution.
Then, for a given skeleton $s=(P_beta, beta, mathcal{D}, mathcal{C})$ and a problem $p$, the following generic function $f_s: Prightarrow S$ computes a solution (in the formal sense) for $p$: $f_s(p)= left{ begin{array}{l l} beta(p) & quad text{if $p$ is basic}\ mathcal{C}(p,f(mathcal{D}(p))) & quad text{otherwise} end{array} right.$ where in the second line we use the notation $f(X) := {f(x) : xin X}$ for subsets $X$ of the codomain of a mapping $f$. However, we did not further examine the underlying, “structural” properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don’t think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles. Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&C-algorithms (not necessarily based on the method outlined above)?
Asked By : Cornelius Brand
Answered By : Cornelius Brand
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14022
