{"ID":2877738,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.20041","arxiv_id":"2508.20041","title":"Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem","abstract":"Motivated by hierarchical networks, we introduce the Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree (FLaMECaST) problem, a variant of the Euclidean Steiner tree with layered structure and capacity constraints per layer. The goal is to construct a cost-optimal Steiner forest connecting a set of sources to a set of sinks under load-dependent edge costs. We prove that FLaMECaST is NP-hard to approximate, even in restricted cases where all sources lie on a circle. However, assuming few additional constraints for such instances, we design a dynamic program that achieves a $\\left(1 + \\frac{1}{2^n}\\right)$-approximation in polynomial time. By generalizing the structural insights the dynamic program is based on, we extend the approach to certain settings, where all sources are positioned on a convex polygon.","short_abstract":"Motivated by hierarchical networks, we introduce the Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree (FLaMECaST) problem, a variant of the Euclidean Steiner tree with layered structure and capacity constraints per layer. The goal is to construct a cost-optimal Steiner forest connecting a set of sources...","url_abs":"https://arxiv.org/abs/2508.20041","url_pdf":"https://arxiv.org/pdf/2508.20041v1","authors":"[\"Thomas Bläsius\",\"Henrik Csöre\",\"Max Göttlicher\",\"Elly Schmidt\",\"Wendy Yi\"]","published":"2025-08-27T16:50:30Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}