Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Greedoid
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Greedy algorithm == In general, a [[greedy algorithm]] is just an iterative process in which a ''locally best choice'', usually an input of maximum weight, is chosen each round until all available choices have been exhausted. In order to describe a greedoid-based condition in which a greedy algorithm is optimal (i.e., obtains a basis of maximum value), we need some more common terminologies in greedoid theory. [[Without loss of generality]], we consider a greedoid {{math|1=''G'' = (''F'', ''E'')}} with {{mvar|E}} finite. A subset {{mvar|X}} of {{mvar|E}} is '''rank feasible''' if the largest intersection of {{mvar|X}} with any feasible set has size equal to the rank of {{mvar|X}}. In a matroid, every subset of {{mvar|E}} is rank feasible. But the equality does not hold for greedoids in general. A function <math>w: E \to \R</math> is '''''R''-compatible''' if <math>\{x \in E: w(x) \geq c\}</math> is rank feasible for all [[real number]]s {{mvar|c}}. An objective function <math>f: 2^S \to \R</math> is '''linear''' over a set <math>S</math> if, for all <math>X \subseteq S,</math> we have <math displaystyle=inline>f(X) = \sum_{x \in X} w(x)</math> for some [[weight function]] <math>w: S \to \Re.</math> '''Proposition.''' A greedy algorithm is optimal for every '''''R'''''-compatible linear objective function over a greedoid. The intuition behind this proposition is that, during the iterative process, each optimal exchange of minimum weight is made possible by the exchange property, and optimal results are obtainable from the feasible sets in the underlying greedoid. This result guarantees the optimality of many well-known algorithms. For example, a [[minimum spanning tree]] of a [[weighted graph]] may be obtained using [[Kruskal's algorithm]], which is a greedy algorithm for the cycle matroid. [[Prim's algorithm]] can be explained by taking the line search greedoid instead.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)