Writing · Tagged
6 articles
The route optimizer benchmark track: JPS was a reasonable pathfinding choice, but precomputed Dijkstra tables, SlotId compression, and an exact ILP referee fit the warehouse better.
How a barcode scan became a warehouse route: order lookup, slot choice, shelf ergonomics, and the graph hidden under a pick list.
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.
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.
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.
An introduction to submodular functions, the mathematical framework behind diminishing returns: set functions, marginal gains, and applications from sensor placement to influence maximization.
The code cited the right weighted-sampling paper and kept the wrong end of its priority queue. The mismatch is more useful than a clean success story.
Karger's min-cut algorithm succeeds on one run with probability at least 2/(n(n-1)), and the same argument proves a graph has at most n(n-1)/2 minimum cuts. Freivalds' check and Miller-Rabin trade a proof for the same kind of bounded failure probability.