IPM and Nested Dissection for Planar and Separable LPs
summary
Combines nested dissection separator trees with a robust interior point method to get concrete solvers: planar min-cost flow in nearly-linear time (m·polylog with polylog ≈ 3–4) and faster routines for planar k‑commodity, low‑treewidth and α‑separable LPs. Key specifics: factor P_w into a tree operator and an inverse via recursive Schur complements, update only affected leaf-to-root ancestors when weights change, keep x implicitly and maintain a coordinatewise approximation x̄, and find heavy coordinates with Johnson‑Lindenstrauss sketches for fast heavy‑hitter detection.
AI-written summary · about