STOC2024
Low-Step Multi-commodity Flow Emulators
Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak
被引用 3 次
摘要
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.