← 研踪 PaperTrailarXiv:2610.17237 · v2
Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More
首次提交 2026-10-13 02:06
版本更新 2026-11-06 00:24
雷达观测 2026-11-06 12:09
摘要
We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout problems and flow-expander decomposition. Using this technique, we obtain state-of-the-art approximation algorithms for several fundamental problems. (1) An $O(\log n)$-approximation for Cutwidth and Pathwidth, improving upon the previous bound of $O(\log n\exp(O(\sqrt{\log\log n})))$ due to Bansal, Katzelnick, and Schwartz (FOCS 2024). This matches the $Ω(\log n)$ integrality gap of the standard LP relaxations. (2) An $O(\log n)$-approximation for their directed analogues, Minimum Storage and Minimum Register Sufficiency on directed acyclic graphs, improving the previous bound of $O(\log^{3/2} n)$. (3) A $φ$-flow-expander decomposition that cuts at most an $O(φ\log n\log\log n)$ fraction of the edges. This improves the $O(φ\log n\exp(O(\sqrt{\log\log n})))$ bound of Bansal, Jambulapati, and Saranurak (ICALP 2026), and is within an $O(\log\log n)$ factor of the graph-theoretic lower bound. The vertex version of our algorithm also gives an $O(\log n)$-approximation for Treedepth. In particular, our results answer several open problems of Bansal, Katzelnick, and Schwartz (FOCS 2024). Technically, we also solve the conceptual question raised by their work: our technique shows how to adapt Seymour recursion to min-max objectives, and constructs $O(1)$-weak local partitions in spreading metrics.
作者备注：46 pages, 5 figures. Corrected cross-reference labels caused by a TeX Live compatibility issue; mathematical content unchanged
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-06 00:24 · 最新观测版本
Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More
We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout problems and flow-expander decomposition. Using this technique, we obtain state-of-the-art approximation algorithms for several fundamental problems. (1) An $O(\log n)$-approximation for Cutwidth and Pathwidth, improving upon the previous bound of $O(\log n\exp(O(\sqrt{\log\log n})))$ due to Bansal, Katzelnick, and Schwartz (FOCS 2024). This matches the $Ω(\log n)$ integrality gap of the standard LP relaxations. (2) An $O(\log n)$-approximation for their directed analogues, Minimum Storage and Minimum Register Sufficiency on directed acyclic graphs, improving the previous bound of $O(\log^{3/2} n)$. (3) A $φ$-flow-expander decomposition that cuts at most an $O(φ\log n\log\log n)$ fraction of the edges. This improves the $O(φ\log n\exp(O(\sqrt{\log\log n})))$ bound of Bansal, Jambulapati, and Saranurak (ICALP 2026), and is within an $O(\log\log n)$ factor of the graph-theoretic lower bound. The vertex version of our algorithm also gives an $O(\log n)$-approximation for Treedepth. In particular, our results answer several open problems of Bansal, Katzelnick, and Schwartz (FOCS 2024). Technically, we also solve the conceptual question raised by their work: our technique shows how to adapt Seymour recursion to min-max objectives, and constructs $O(1)$-weak local partitions in spreading metrics.
查看此版本解读 →查看此版本原文 ↗