{"ID":2840644,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.13806","arxiv_id":"2511.13806","title":"Optimal Sequential Flows","abstract":"We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximise the flow through a graph where edge capacities can be changed over time by choosing a sequence of capacity labelings from a given finite set. Our method is based on a novel factorization theorem for finite semigroups that, applied to a suitable flow semigroup, allows to derive small witnesses. This generalises to multiple in/output vertices, as well as regular constraints.","short_abstract":"We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximise the flow through a graph where edge capacities can be changed over time by choosing a sequence of capacity labelings from a given finite set. Our method is based on a novel factorization theorem for fi...","url_abs":"https://arxiv.org/abs/2511.13806","url_pdf":"https://arxiv.org/pdf/2511.13806v2","authors":"[\"Hugo Gimbert\",\"Corto Mascle\",\"Patrick Totzke\"]","published":"2025-11-17T15:05:06Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\",\"cs.FL\"]","methods":"[]","has_code":false}