When Addition Becomes Optimization: Tropical Algebra, Paths, Schedules, and Semiring Computation
Abstract
Changing the arithmetic changes what linear algebra means. In tropical algebra, ordinary addition is replaced by min or max, and ordinary multiplication is replaced by addition. That one substitution turns shortest-path computation, Bellman recurrences, critical-path scheduling, and synchronized event systems into variations on the same matrix-algebraic theme. This paper traces a single small weighted graph through min-plus and max-plus arithmetic, connecting each algebraic operation to a concrete computational or scheduling interpretation. The goal is not to claim that tropical algebra makes hard problems easy, but to show that it reveals the algebraic structure underneath a wide class of path, timing, and propagation computations.
Status
PDF forthcoming. The preprint will be posted here, together with its DOI, when it is released.
Interactive supporting information
The paper’s computations can be explored step by step in the browser — four self-contained artifacts, one per part of the story, all built on the same running example:
- Matrix multiplication, three arithmetics — the interactive twin of Figure 2: click a product cell, see its candidates, switch the semiring (Section 3).
- Shortest paths as relaxation schedules — Bellman–Ford (synchronous and in-place), Dijkstra, min-plus powers (raw W and A = I ⊕ W), and the full max-plus CPM with backward pass and slack (Sections 4–8).
- Inside a tropical GEMM kernel — the tiled (min, +) kernel animated: shared-memory staging and the accumulator loop with no FMA (Section 9).
- Cyclic schedules and the max-plus eigenvalue — trajectories, transients, eigenvectors, and the bottleneck cycle’s cadence, with weight sliders and the exact λ(w) sensitivity curve (Sections 10–11).