Benchmark: Greedy + ε-exploration

[alltheseas]

Summary

Add ε-greedy exploration to the greedy set-cover algorithm: with probability ε (e.g. 5%), pick a random relay instead of the max-coverage one.

Why

Greedy set-cover has catastrophic long-term recall (10% at 3yr) because it always picks the same popular relays that may have pruned old events. A small random exploration factor would occasionally discover relays that retain history, likely fixing the degradation without meaningfully hurting short-term coverage.

What to do

1. Add an epsilon parameter (default 0.05) to the greedy algorithm
2. Before each relay selection step, with probability ε pick a random candidate instead of the highest-coverage one
3. Benchmark across all 6 time windows, comparing against vanilla greedy

function selectNextRelay(candidates, epsilon = 0.05) {
  if (Math.random() < epsilon) {
    return candidates[Math.floor(Math.random() * candidates.length)];
  }
  return candidates.sort((a, b) => b.uncoveredCount - a.uncoveredCount)[0];
}

Effort

Low — one if statement in the greedy loop.

Reference

• IMPLEMENTATION-GUIDE.md: Improvement Opportunities (low effort)