arXiv:2607.29160 · Geometric Maximum Coverage

Squares Coverage Showdown

A 10×10 Super Bowl squares grid, weighted by real NFL final-score last-digit frequency. Instead of buying single squares, you're buying rectangular zones — blocks of squares, the kind of geometric object (axis-aligned "fat rectangles") the paper studies. Pick a budget of k zones. Zones overlap, so the order and choice of picks matters — and plain greedy selection provably leaves probability mass on the table.

Approximation Algorithms for Geometric Maximum Coverage — arxiv.org/abs/2607.29160
how this works Points = the 100 weighted squares (weight = product of each digit's real NFL last-digit frequency). Objects = every axis-aligned zone of shape 1×1, 2×2, 3×3, and the long 7×2 / 2×7 "bar" zones that fits on the board — a live-generated candidate pool (hundreds of zones), not a fixed list. Greedy repeatedly adds the zone with the highest marginal weight gain. Near-optimal starts from greedy, then runs a real swap-based local search (try every selected↔unselected zone swap, keep improving moves) across a couple of randomized restarts, and keeps the best result found. The bars overlap the squares just enough that greedy's early picks lock in waste — drag k into the 5–12 range to watch a real, nonzero gap open up, then close again once the budget is big enough to blanket the board either way. That opening-then-closing gap is exactly the "greedy isn't enough, but you can do much better in poly-time" story the paper proves for pseudodisks and fat rectangles.
9
candidate pool: — zones
—
Greedy coverage
—
Near-optimal coverage
—
Gap left on the table
—
Relative lift
Greedy pick (k zones)
Near-optimal pick (k zones)
Where the two selections disagree
covered only by near-optimal covered only by greedy covered by both uncovered