Greedy Algorithm Ontology

FLOW ALGEBRA
GREEDY ALGORITHM ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/greedy-algorithm-ontology-2.html
Domain: Discrete Mathematics > Algorithmic Mathematics > Greedy Algorithms
Authors: Mark Higgins — Sky (Recursive AI)
Publisher: Kireth Research | https://kirethresearch.org
Date: 2026-10-11

1. PURPOSE
Model greedy algorithms as constructive optimisation procedures that make locally preferred feasible choices, and specify the conditions under which these choices produce globally optimal solutions.

2. TYPED ENTITIES
entity Problem : OptimisationProblem
entity Instance : ProblemInstance
entity GroundSet : FiniteSet[Candidate]
entity Candidate : DecisionElement
entity PartialSolution : Sequence[Candidate] | Set[Candidate]
entity FeasibleSolution : Solution
entity Objective : Function[Solution, Real]
entity FeasibilityPredicate : Predicate[Solution]
entity ChoiceRule : Function[PartialSolution, Set[Candidate], Candidate]
entity GreedyAlgorithm : Algorithm
entity GreedyChoiceProperty : ProofObligation
entity OptimalSubstructure : ProofObligation
entity ExchangeArgument : ProofTechnique
entity Invariant : LogicalPredicate
entity OptimalSolution : FeasibleSolution
entity TieBreakingRule : DeterministicRule
entity Counterexample : ProblemInstance
entity ComplexityBound : AsymptoticBound
entity Matroid : IndependenceSystem

3. RELATIONSHIPS
relationship solves(GreedyAlgorithm, Problem)
relationship hasInstance(Problem, Instance)
relationship hasCandidates(Instance, GroundSet)
relationship evaluates(Objective, FeasibleSolution)
relationship constrainedBy(PartialSolution, FeasibilityPredicate)
relationship selects(ChoiceRule, Candidate)
relationship extends(PartialSolution, Candidate)
relationship preserves(GreedyAlgorithm, Invariant)
relationship requiresProof(GreedyAlgorithm, GreedyChoiceProperty)
relationship supportsProof(ExchangeArgument, GreedyChoiceProperty)
relationship witnessesFailure(Counterexample, GreedyAlgorithm)
relationship boundedBy(GreedyAlgorithm, ComplexityBound)

4. FORMAL PROBLEM MODEL
input I = (E, F, w, goal)
E : finite candidate ground set
F subseteq P(E) : feasible solutions (or feasible sequences)
w : F -> Real : objective
 goal in {minimise, maximise}
Find S* in F such that for all S in F:
  goal = minimise => w(S*) <= w(S)
  goal = maximise => w(S*) >= w(S)

5. GREEDY CONSTRUCTION FLOW
flow GreedyConstruct(I):
  require finite(I.E)
  S := empty partial solution
  R := available candidates(I)
  while not complete(S, I) and R != empty:
    A := {x in R | feasible_extension(S, x, I)}
    if A = empty: break
    x := argbest(A, local_score(x, S, I), tie_break)
    S := extend(S, x)
    R := update_candidates(R, x, S, I)
    assert partial_feasibility(S, I)
  return S
postcondition: partial_feasibility(S, I)
NOTE: Global optimality is NOT a generic postcondition; it requires a problem-specific proof.

6. INFERENCE RULES
rule FeasibleExtension:
  feasible_partial(S) AND feasible_extension(S,x) => feasible_partial(extend(S,x))
rule LocalSelection:
  x in admissible(S) AND forall y in admissible(S), score(x) >= score(y)
  => greedy_choice(x,S)  [maximisation score]
rule ExchangeCertificate:
  exists optimal O containing a compatible greedy choice x, with no worse objective
  => greedy choice is safe for that state
rule InductiveOptimality:
  safe_greedy_choice(S,x) AND optimal_residual_subproblem(extend(S,x))
  => optimal_completion(S)
rule Counterexample:
  exists I with feasible(GreedyConstruct(I)) AND objective(GreedyConstruct(I)) worse than optimum(I)
  => NOT universally_optimal(GreedyConstruct)

7. CORRECTNESS OBLIGATIONS
O1: Every accepted choice preserves feasibility.
O2: Each iteration makes measurable progress and terminates.
O3: Chosen element is safe: some optimum is consistent with it.
O4: Residual problem preserves the conditions needed for the next safe choice.
O5: On termination, the solution is complete and optimal.
O6: Tie-breaking does not invalidate the proof (or restrictions are specified).

8. PROOF PATTERNS
- Exchange argument: transform an optimum to include the greedy choice without loss.
- Stays-ahead argument: show greedy prefix is at least as good as any competitor prefix.
- Cut property: show the chosen edge is safe across a graph cut.
- Matroid theorem: weight-sorted greedy yields a maximum-weight basis for a matroid.
- Loop invariant: maintain feasibility and compatibility with some optimum.

9. CANONICAL EXAMPLES
example ActivitySelection:
  input: intervals with start and finish times
  goal: maximum cardinality non-overlapping subset
  choice: earliest finishing compatible activity
  guarantee: optimal for unweighted activity selection
  typical complexity: O(n log n) sorting + O(n) scan

example MinimumSpanningTree_Kruskal:
  input: connected undirected weighted graph
  choice: minimum-weight edge that does not create a cycle
  guarantee: minimum spanning tree via cut/exchange property
  typical complexity: O(E log E) with efficient disjoint-set operations

example FractionalKnapsack:
  input: divisible items, positive weights, values, capacity
  choice: decreasing value/weight ratio
  guarantee: optimal fractional solution
  typical complexity: O(n log n) sorting

example Dijkstra:
  input: graph with nonnegative edge weights, source vertex
  choice: unsettled vertex with smallest tentative distance
  guarantee: correct shortest-path distances under nonnegative weights
  note: negative edges invalidate the generic correctness guarantee

10. FAILURE CASES AND SCOPE
counterexample CoinChange:
  denominations = {1,3,4}; target = 6
  largest-first greedy = 4+1+1 (3 coins)
  optimum = 3+3 (2 coins)
  conclusion: greedy coin change is not universally optimal

counterexample ZeroOneKnapsack:
  capacity = 50
  items (weight,value) = {(10,60),(20,100),(30,120)}
  ratio-greedy picks weights 10 and 20, value 160
  optimum picks weights 20 and 30, value 220
  conclusion: fractional guarantee does not transfer to 0/1 knapsack

11. COMPLEXITY MODEL
T(n) = T_rank(n) + T_feasibility(n) + T_updates(n)
Space(n) = storage(partial_solution, candidate_set, auxiliary_structures)
Sorting-based greedy often costs O(n log n), but complexity is instance-specific.

12. SEMANTIC EQUIVALENCE
semantic_equivalence:
  "greedy method" <=> "greedy algorithm design paradigm" [context: algorithm design]
  "locally optimal choice" ~= "greedy selection" [context: admissible candidates]
  "greedy-choice property" != "optimal substructure"
  "greedy heuristic" != "proven optimal greedy algorithm"
  "fractional knapsack" != "0/1 knapsack"

13. VALIDATION
validate finite_candidate_set
validate well_defined_feasibility
validate deterministic_or_documented_tie_breaking
validate termination_measure
validate objective_and_goal
validate proof_of_safe_choice_if_optimality_claimed
validate residual_subproblem_assumptions
validate counterexamples_against_universal_claims
validate complexity_assumptions

14. CONFIDENCE
confidence:
  formal_definitions: high
  classical_example_guarantees: high_under_stated_assumptions
  new_problem_optimality: unverified_until_proved
  heuristic_performance: empirical_and_instance_dependent

15. FLOW_HASH
flow_hash:
  method: SHA-256
  scope: canonical UTF-8 file bytes
  value: compute_after_final_publication
  note: no fabricated digest; regenerate on content change

16. UPDATE_MODEL
update_model:
  version: 1.0
  change_policy: semantic_versioning
  triggers: [new_proof, corrected_counterexample, refined_constraints, new_algorithm_family]
  preserve: [canonical_url, provenance, historical_versions]
  validation_on_update: all_checks

17. AI_CONSUMPTION
ai_consumption:
  representation: typed_semantic_flow
  reasoning_modes: [classification, feasibility_checking, proof_obligation_tracking, complexity_analysis, counterexample_search]
  distinguish: [locally_optimal, globally_optimal, heuristic, exact]
  retrieval_keys: [greedy_algorithm, greedy_choice_property, exchange_argument, matroid, activity_selection, kruskal, fractional_knapsack]
  hallucination_guard: never_infer_global_optimality_from_local_choice_alone
  evidence_policy: state_preconditions_and_proof_before_optimality_claim

18. CROSS-ONTOLOGY LINKS
related: Algorithm Ontology
related: Recursive Algorithm Ontology
related: Divide and Conquer Ontology
related: Dynamic Programming Ontology
related: Graph Algorithm Ontology
related: Optimisation Ontology
related: Computational Complexity Ontology

END FLOW ALGEBRA