What does Most Conflicts Are Redundancy conclude, in numbers, about “Greedy Set Cover and ln n: Provable Bounds on a Minimal Primitive Set”?

Answer: Chapter 5 gives the bounds and a gap certificate for greedy set cover, which on ordinary instances is off by a mean factor of only 1.0919.

Scope of the numbers: The rule libraries and values are illustrative; every calculation is generated by the book's programs; the book offers general business method, not legal, compliance or business-decision advice, and adding or deleting a rule must be released by its owner. Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1.0919

300 instances40 rules, 25 candidate primitives, seed 20261113
greedy uses 0 more than the minimum127 instances
greedy uses 1 more than the minimum145 instances
greedy uses 2 more than the minimum27 instances
greedy uses 3 more than the minimum1 instances
median minimum cover 7 primitives (range 6 to 11)
mean ratio greedy / minimum1.0919
worst ratio observed1.4286
Johnson bound H(12)3.1032 (ln 12 + 1 = 3.4849)
Show the full program
# Chapter 5. p51: greedy primitive selection against the true minimum
# Model: 40 written rules must each be derivable from at least one
# chosen primitive; 25 candidate primitives each derive a random
# subset of the rules (sizes 2 to 12, illustrative), with every rule
# derivable from some candidate. Greedy (Johnson 1974; Lovasz 1975):
# repeatedly take the primitive deriving most still-uncovered rules,
# ties to the lowest index. The minimum is found by branch and bound.
# Johnson's guarantee: greedy / minimum <= H(k), k the largest set,
# H the harmonic number, computed exactly with Fraction. 300
# instances, one fixed seed.

import math
import random
from collections import Counter
from fractions import Fraction as F


def harmonic(k):
    h = F(0)
    for i in range(1, k + 1):
        h += F(1, i)
    return h


def greedy(sets, full):
    cov, k = 0, 0
    while cov != full:
        best = max(range(len(sets)),
                   key=lambda i: (bin(sets[i] & ~cov).count("1"), -i))
        cov |= sets[best]
        k += 1
    return k


def exact(sets, full, start):
    best = [start]

    def go(cov, k):
        if cov == full:
            best[0] = min(best[0], k)
            return
        if k + 1 >= best[0]:
            return
        left = full & ~cov
        pick, cands = None, None
        b = 0
        while left:
            if left & 1:
                cs = [s for s in sets if (s >> b) & 1]
                if cands is None or len(cs) < len(cands):
                    pick, cands = b, cs
            left >>= 1
            b += 1
        for s in sorted(cands, key=lambda s: -bin(s & ~cov).count("1")):
            go(cov | s, k + 1)
    go(0, 0)
    return best[0]


def instance(rng, n=40, m=25):
    while True:
        sets = []
        for _ in range(m):
            k = rng.randint(2, 12)
            bits = 0
            for e in rng.sample(range(n), k):
                bits |= 1 << e
            sets.append(bits)
        full = (1 << n) - 1
        allc = 0
        for s in sets:
            allc |= s
        if allc == full:
            return sets, full


rng = random.Random(20261113)
ratios = []
gaps = Counter()
opts = []
for _ in range(300):
    sets, full = instance(rng)
    g = greedy(sets, full)
    o = exact(sets, full, g)
    ratios.append(F(g, o))
    opts.append(o)
    gaps[g - o] += 1
worst = max(ratios)
print("300 instances: 40 rules, 25 candidate primitives, seed 20261113")
for d in sorted(gaps):
    print("   greedy uses %d more than the minimum: %3d instances"
          % (d, gaps[d]))
print("median minimum cover %d primitives (range %d to %d)"
      % (sorted(opts)[150], min(opts), max(opts)))
print("mean ratio greedy / minimum  %.4f"
      % (math.fsum(float(r) for r in ratios) / 300))
print("worst ratio observed         %.4f" % worst)
print("Johnson bound H(12)          %.4f   (ln 12 + 1 = %.4f)"
      % (harmonic(12), math.log(12) + 1))

Single source and citation

Fan, Y. (2026). Cross-Volume Rule Resolution and Axiom Reduction: Detecting Threshold Conflicts among a Thousand Machine Rules and Finding a Minimal Primitive Set (Version 1.0.0), Chapter 5: Greedy Set Cover and ln n: Provable Bounds on a Minimal Primitive Set. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-258 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026258,
  author    = {Fan, Yafu},
  title     = {Cross-Volume Rule Resolution and Axiom Reduction: Detecting Threshold Conflicts among a Thousand Machine Rules and Finding a Minimal Primitive Set},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book