Search Results

Documents authored by Naves, Guyslain

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.12
Uncrossed Multiflows and Applications to Disjoint Paths

Authors: Chandra Chekuri, Guyslain Naves, Joseph Poremba, and F. Bruce Shepherd

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
A multiflow in a planar graph is uncrossed if the curves identified by its support paths do not cross in the plane. Recently, uncrossed flows have played a role in approximation algorithms for maximum disjoint paths in "fully-planar" instances, where the combined supply-plus-demand graph is planar. They are also used in algorithms to find low-congestion unsplittable flows for both fully-planar and single-source instances. For these two instance classes, any fractional multiflow can be converted into one that is uncrossed, which these algorithms then exploit to obtain their results. We investigate the utility of uncrossed flow more generally and ask three key questions. First, are there other interesting planar multiflow instances that admit uncrossed flows (beyond fully-planar and single-source)? We answer affirmatively, demonstrating a new family of "pairwise-planar" instances whose fractional flows can be uncrossed. This family subsumes fully-planar but includes substantially more, such as (2-connected) fully-compliant series-parallel instances and some instances that have large clique demand graphs. Second, can we always round a fractional uncrossed flow to a "good" integral flow? We again answer positively. For maximization problems, we show any fractional uncrossed flow can be rounded to an integral flow with a constant fraction of its value. For congestion problems (where we must fully route all given demands), we give a rounding procedure that yields an integral multiflow with edge congestion 2. Consequently, we obtain constant-factor approximation algorithms for maximum disjoint paths and minimum congestion integer multiflow for pairwise-planar instances, and show such instances have a constant integral flow-multicut gap. Finally we ask, given an arbitrary planar instance, can we determine if there exists a congestion-1 uncrossed fractional flow (congestion setting) or find the maximum value uncrossed fractional flow (maximization setting)? For congestion, we show this problem is NP-hard, but finding uncrossed edge-disjoint paths is polytime solvable if the demands span a bounded number of faces. For maximization, we present a strong (almost-polynomial) inapproximability result.
Cite as

Chandra Chekuri, Guyslain Naves, Joseph Poremba, and F. Bruce Shepherd. Uncrossed Multiflows and Applications to Disjoint Paths. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 12:1-12:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2026.12,
  author =	{Chekuri, Chandra and Naves, Guyslain and Poremba, Joseph and Shepherd, F. Bruce},
  title =	{{Uncrossed Multiflows and Applications to Disjoint Paths}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{12:1--12:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.12},
  URN =		{urn:nbn:de:0030-drops-277298},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.12},
  annote =	{Keywords: Network Flows, Disjoint Paths, Planar Graphs, Crossing, Flow-Multicut Gap, Approximation Algorithms, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.9
The Steady-States of Splitter Networks

Authors: Basile Couëtoux, Bastien Gastaldi, and Guyslain Naves

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
We introduce splitter networks, which abstract the behavior of conveyor belts found in the video game Factorio. Based on this definition, we show how to compute the steady-state of a splitter network. Then, leveraging insights from the players community, we provide multiple designs of splitter networks capable of load-balancing among several conveyor belts, and prove that any load-balancing network on n belts must have Ω(n log n) nodes. Incidentally, we establish connections between splitter networks and various concepts including flow algorithms, flows with equality constraints, Markov chains and the Knuth-Yao theorem about sampling over rational distributions using a fair coin.
Cite as

Basile Couëtoux, Bastien Gastaldi, and Guyslain Naves. The Steady-States of Splitter Networks. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{couetoux_et_al:LIPIcs.FUN.2024.9,
  author =	{Cou\"{e}toux, Basile and Gastaldi, Bastien and Naves, Guyslain},
  title =	{{The Steady-States of Splitter Networks}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.9},
  URN =		{urn:nbn:de:0030-drops-199174},
  doi =		{10.4230/LIPIcs.FUN.2024.9},
  annote =	{Keywords: Factorio, splitter networks, flow, balancer, steady-state}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact