847 Advanced

Approximation Algorithm — Set Cover

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Approximation Algorithm — Set Cover" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Set cover is NP-hard: given a universe U of elements and a collection S of subsets, find the minimum number of subsets whose union equals U. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Set cover is NP-hard: given a universe U of elements and a collection S of subsets, find the minimum number of subsets whose union equals U. The greedy approximation picks the subset covering the most uncovered elements at each step, achieving an O(log n) approximation — proven optimal assuming P ≠ NP. This approximation is used in: network monitoring (minimum sensor placement to cover all traffic), advertising (minimum campaigns to reach all demographics), feature selection in machine learning, and compiler register allocation. Understanding approximation algorithms — which sacrifice optimality for polynomial time — is essential for NP-hard optimization.

🎯 Learning Outcomes

• Implement the greedy set cover approximation: at each step, pick the set covering most uncovered elements

• Understand the O(ln n) approximation ratio: greedy covers at least 1/OPT fraction at each step

• Recognize when approximation is appropriate: NP-hard problems in practice

• Compare greedy approximation ratio against brute-force optimal on small instances

• Apply the technique to vertex cover, dominating set, and other NP-hard problems with similar guarantees

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Greedy Set Cover Approximation in OCaml *)

module IntSet = Set.Make(Int)

(* Greedy set cover: always pick the set covering the most uncovered elements *)
(* Returns list of chosen set indices *)
let greedy_set_cover (universe : int list) (sets : int list list) : int list =
  let uncovered = ref (IntSet.of_list universe) in
  let remaining_sets = ref (List.mapi (fun i s -> (i, IntSet.of_list s)) sets) in
  let chosen = ref [] in
  while not (IntSet.is_empty !uncovered) && not (List.is_empty !remaining_sets) do
    (* Find set with maximum coverage of uncovered elements *)
    let best = List.fold_left (fun best_opt (i, s) ->
      let covered = IntSet.cardinal (IntSet.inter s !uncovered) in
      match best_opt with
      | None -> Some (i, s, covered)
      | Some (_, _, best_cov) ->
        if covered > best_cov then Some (i, s, covered) else best_opt
    ) None !remaining_sets in
    match best with
    | None -> ()
    | Some (i, s, _) ->
      chosen := i :: !chosen;
      uncovered := IntSet.diff !uncovered s;
      remaining_sets := List.filter (fun (j, _) -> j <> i) !remaining_sets
  done;
  List.rev !chosen

(* Weighted set cover: each set has a cost; choose minimum-cost cover *)
(* Greedy: pick set with lowest cost per new element covered *)
let greedy_weighted_set_cover
    (universe : int list) (sets : (int list * float) list) : int list =
  let uncovered = ref (IntSet.of_list universe) in
  let indexed = List.mapi (fun i (s, cost) -> (i, IntSet.of_list s, cost)) sets in
  let remaining = ref indexed in
  let chosen = ref [] in
  while not (IntSet.is_empty !uncovered) && not (List.is_empty !remaining) do
    let best = List.fold_left (fun best_opt (i, s, cost) ->
      let new_covered = IntSet.cardinal (IntSet.inter s !uncovered) in
      if new_covered = 0 then best_opt
      else
        let ratio = cost /. float_of_int new_covered in
        match best_opt with
        | None -> Some (i, s, ratio)
        | Some (_, _, best_r) -> if ratio < best_r then Some (i, s, ratio) else best_opt
    ) None !remaining in
    match best with
    | None -> ()
    | Some (i, s, _) ->
      chosen := i :: !chosen;
      uncovered := IntSet.diff !uncovered s;
      remaining := List.filter (fun (j, _, _) -> j <> i) !remaining
  done;
  List.rev !chosen

let () =
  (* Classic example *)
  let universe = [1;2;3;4;5;6;7;8;9;10] in
  let sets = [
    [1;2;3;4;5];
    [4;5;6;7;8];
    [1;3;5;7;9];
    [2;4;6;8;10];
    [6;7;8;9;10];
  ] in
  let chosen = greedy_set_cover universe sets in
  Printf.printf "Greedy set cover (unweighted):\n";
  Printf.printf "  Chosen sets (0-indexed): [%s]\n"
    (String.concat "; " (List.map string_of_int chosen));
  Printf.printf "  Number of sets: %d\n" (List.length chosen)

Key Differences

Aspect	Rust	OCaml
Universe set	`HashSet<u32>`	`Set.Make(Int).t` or `Hashtbl`
Intersection count	`.intersection().count()`	`Set.inter \\|> Set.cardinal`
Best set selection	`max_by_key`	`List.fold_left` with max
Uncovered removal	`retain(\|e\| !contains)`	`Set.diff uncovered chosen`
Approximation ratio	O(ln n) provable	Same
Brute force comparison	Exponential search	Same

OCaml Approach

OCaml implements greedy set cover with a Hashtbl for the uncovered set or a Set.Make(Int) balanced BST. List.fold_left finds the maximum-coverage set. Set.inter uncovered s |> Set.cardinal counts intersections. OCaml's Set.diff uncovered chosen_set removes covered elements immutably. The while loop or tail recursion drives iteration. List.rev restores selection order if building the list by prepending.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Greedy Set Cover Approximation in OCaml *)

module IntSet = Set.Make(Int)

(* Greedy set cover: always pick the set covering the most uncovered elements *)
(* Returns list of chosen set indices *)
let greedy_set_cover (universe : int list) (sets : int list list) : int list =
  let uncovered = ref (IntSet.of_list universe) in
  let remaining_sets = ref (List.mapi (fun i s -> (i, IntSet.of_list s)) sets) in
  let chosen = ref [] in
  while not (IntSet.is_empty !uncovered) && not (List.is_empty !remaining_sets) do
    (* Find set with maximum coverage of uncovered elements *)
    let best = List.fold_left (fun best_opt (i, s) ->
      let covered = IntSet.cardinal (IntSet.inter s !uncovered) in
      match best_opt with
      | None -> Some (i, s, covered)
      | Some (_, _, best_cov) ->
        if covered > best_cov then Some (i, s, covered) else best_opt
    ) None !remaining_sets in
    match best with
    | None -> ()
    | Some (i, s, _) ->
      chosen := i :: !chosen;
      uncovered := IntSet.diff !uncovered s;
      remaining_sets := List.filter (fun (j, _) -> j <> i) !remaining_sets
  done;
  List.rev !chosen

(* Weighted set cover: each set has a cost; choose minimum-cost cover *)
(* Greedy: pick set with lowest cost per new element covered *)
let greedy_weighted_set_cover
    (universe : int list) (sets : (int list * float) list) : int list =
  let uncovered = ref (IntSet.of_list universe) in
  let indexed = List.mapi (fun i (s, cost) -> (i, IntSet.of_list s, cost)) sets in
  let remaining = ref indexed in
  let chosen = ref [] in
  while not (IntSet.is_empty !uncovered) && not (List.is_empty !remaining) do
    let best = List.fold_left (fun best_opt (i, s, cost) ->
      let new_covered = IntSet.cardinal (IntSet.inter s !uncovered) in
      if new_covered = 0 then best_opt
      else
        let ratio = cost /. float_of_int new_covered in
        match best_opt with
        | None -> Some (i, s, ratio)
        | Some (_, _, best_r) -> if ratio < best_r then Some (i, s, ratio) else best_opt
    ) None !remaining in
    match best with
    | None -> ()
    | Some (i, s, _) ->
      chosen := i :: !chosen;
      uncovered := IntSet.diff !uncovered s;
      remaining := List.filter (fun (j, _, _) -> j <> i) !remaining
  done;
  List.rev !chosen

let () =
  (* Classic example *)
  let universe = [1;2;3;4;5;6;7;8;9;10] in
  let sets = [
    [1;2;3;4;5];
    [4;5;6;7;8];
    [1;3;5;7;9];
    [2;4;6;8;10];
    [6;7;8;9;10];
  ] in
  let chosen = greedy_set_cover universe sets in
  Printf.printf "Greedy set cover (unweighted):\n";
  Printf.printf "  Chosen sets (0-indexed): [%s]\n"
    (String.concat "; " (List.map string_of_int chosen));
  Printf.printf "  Number of sets: %d\n" (List.length chosen)

Deep Comparison

OCaml vs Rust: Approximation Set Cover

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement brute-force optimal set cover (exponential) for small instances and compare with greedy approximation ratio.

Implement the LP relaxation of set cover and show its integrality gap matches the greedy bound.

Apply greedy set cover to a sensor placement problem: cover all n points in a plane with minimum unit-radius circles.

Implement a weighted set cover: each subset has a cost, minimize total cost using the cost-effectiveness greedy.

Measure approximation quality empirically: for random instances, how close does greedy come to optimal?

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust