Randomized, Approximation, and Online Algorithms

Randomized algorithm analysis, approximation ratio, greedy approximation, set cover overview, scheduling approximation, online decisions, competitive ratio, streaming algorithms, and reservoir sampling.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

An approximation algorithm comes with a proof: the vertex-cover algorithm picks edges that share no endpoints (a matching), and any cover needs one endpoint per matched edge, so the result is at most twice optimal. A heuristic has no such guarantee.

Competitive ratio compares an online algorithm (deciding without the future) with the best offline choice; the rent-then-buy strategy is (2 − 1/B)-competitive, and no deterministic strategy does better.

Greedy set cover is within a factor H(max set size) ≤ ln n + 1 of optimal — in the run it picked 3 sets where 2 suffice; set cover is NP-hard to approximate much better.

Streaming algorithms use sublinear memory: reservoir sampling (Module 51), Count-Min sketches for frequencies, HyperLogLog for distinct counts.

#include <bits/stdc++.h>
using namespace std;

int main() {
    mt19937 rng(27);
    // vertex cover: take both endpoints of any uncovered edge -> at most 2 x optimal
    double worstRatio = 0;
    for (int t = 0; t < 300; ++t) {
        int n = rng() % 10 + 2; vector<pair<int, int>> e;
        for (int k = 0; k < n * 2; ++k) { int u = rng() % n, v = rng() % n; if (u != v) e.push_back({u, v}); }
        vector<bool> in(n, false); int approx = 0;
        for (auto [u, v] : e) if (!in[u] && !in[v]) { in[u] = in[v] = true; approx += 2; }
        int opt = n;
        for (int mask = 0; mask < 1 << n; ++mask) {
            bool ok = true; for (auto [u, v] : e) ok &= (mask >> u & 1) || (mask >> v & 1);
            if (ok) opt = min(opt, __builtin_popcount(mask));
        }
        if (opt) worstRatio = max(worstRatio, double(approx) / opt);
    }
    cout << "vertex cover 2-approximation, worst ratio over 300 random graphs: " << worstRatio << " (guarantee: <= 2)\n";

    // ski rental: rent costs 1/day, buying costs B. Rent until the rental total would reach B, then buy.
    int B = 10; double worst = 0;
    for (int days = 1; days <= 50; ++days) {
        int online = days < B ? days : 
…

vertex cover 2-approximation, worst ratio over 300 random graphs: 2 (guarantee: <= 2)
ski rental with B = 10: worst competitive ratio over 1..50 days = 1.9 (theory 2 - 1/B = 1.9)
greedy set cover picked sets: 0 2 3 (3 sets)
optimal number of sets by brute force: 2

Quiz

? What distinguishes an approximation algorithm from a heuristic?
+ A proven bound on how far its result can be from optimal :: The 2-approximation never exceeded ratio 2.
- It is faster :: Not necessarily.
- It uses randomness :: Not necessarily.
- It always finds the optimum :: Then it would be exact.

? Why is the matching-based vertex cover at most twice optimal?
+ The chosen edges share no endpoints, and any cover must include at least one endpoint of each, so OPT ≥ (chosen edges) and the result is 2 × that. :: A lower bound from the matching.
- It picks vertices of highest degree :: That is a different heuristic.
- It is exactly optimal on trees :: Not this algorithm.
- Because 2 is the number of endpoints, by definition :: The proof needs the lower bound.

? In ski rental with B = 10, what does a competitive ratio of 1.9 mean?
+ The online cost is never more than 1.9 times the cost of an omniscient buyer :: Worst over all possible numbers of ski days.
- It is 1.9 times faster :: No.
- It costs 1.9 per day :: No.
- It is wrong 10% of the time :: No.