· 6 min read
Splitmix32: Thirteen Lines of Beautiful Randomness
I went looking for a seeded PRNG in TypeScript and found splitmix32, a 32-bit pseudorandom number generator so elegant it made me want to understand every single bit.
Writing · Tagged
#math
5 articles
· 9 min read · Part 4 of 4
Stochastic Greedy: Scaling Submodular Maximization to Massive Datasets
Stochastic Greedy replaces greedy's full scan with random subsampling, reducing runtime from O(nk) to O(n ln(1/ε)) while losing only an additive ε in the approximation guarantee. This post covers the algorithm, its proof, and practical guidance.
· 6 min read · Part 3 of 4
Lazy Greedy: Speeding Up Submodular Maximization for Free
Lazy Greedy keeps the greedy algorithm's (1 - 1/e) guarantee while skipping most of its oracle calls. Submodularity makes stale marginal gains sound upper bounds, so a max-heap of them is enough to certify each pick.
· 12 min read · Part 2 of 4
The Greedy Algorithm for Submodular Maximization
The greedy algorithm achieves a (1 - 1/e) approximation for monotone submodular maximization, provably the best any efficient algorithm can do. This post covers the algorithm, its proof, and when greedy fails.
· 16 min read · Part 1 of 4
An Introduction to Submodularity
An introduction to submodular functions, the mathematical framework behind diminishing returns: set functions, marginal gains, and applications from sensor placement to influence maximization.