Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
Thomas Bläsius, Henrik Csöre, Max Göttlicher, Elly Schmidt, Wendy Yi · 2025
Read Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem by Thomas Bläsius, Henrik Csöre, Max Göttlicher, Elly Schmidt, Wendy Yi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20041.txt.
Introduction
Thomas Bläsius and co-authors define a layered Steiner tree problem with flow costs in a 2025 paper. Hierarchical networks stack layers, each with capacity limits. Sources must reach sinks cheaply while edge prices grow with load. The Euclidean plane hosts the geometry.
The team prove the problem is hard even to approximate, even when sources sit on a circle. Restrict those circle cases a little more, though, and a dynamic program wins near-perfect approximations in polynomial time. Its structural tricks extend to sources on any convex polygon. The boundary between hopeless and tractable runs through the geometry of the source set.
Catalog record
| CREATOR | Thomas Bläsius, Henrik Csöre, Max Göttlicher, Elly Schmidt, Wendy Yi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 123 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20041
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem Thomas Bläsius, Henrik Csöre, Max Göttlicher, Elly Schmidt, Wendy Yi 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 ( 1 + 1 2 n ) \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. \todostyle mgprepend,caption=MG,color=color3 \todostyle tbprepend,caption=TB,color=color0 \todostyle wyprepend,caption=WY,color=color1 Karlsruhe Institute of Technology Karlsruhe Institute of Technology Karlsruhe Institute of Technology Karlsruhe Institute of Technology Karlsruhe Institute of Technology {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10003636¡/concept_id¿ ¡concept_desc¿Theory of computation Approximation algorithms analysis¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003777.10003779¡/concept_id¿ ¡concept_desc¿Theory of computation Problems, reductions and completeness¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Approximation algorithms analysis ccs Theory of computation Problems, reductions and completeness keywords euclidean steiner tree, dynamic programming, network design, approximation algorithms † † runningauthor: T. Bläsius, H. Csöre, M. Göttlicher, E. Schmidt, W. Yi † † copyright: Thomas Bläsius, Henrik Csöre, Max Göttlicher, Elly Schmidt and Wendy Yi † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Many applications, like connecting households with electricity or water, connecting solar panels to the power grid, planning logistics systems or in general various facility location problems, boil down to finding a graph that satisfies certain needs while being cost efficient. Often, a fundamental goal in these network design problems is to minimize the cost to connect all components. While this goal can be modeled as the well-known Minimum Spanning Tree (MST) problem, it often fails to capture other requirements by the application. A common generalization is the Steiner tree [ 9 ] , which allows the use of Steiner vertices that can be – but do not have to be – included in the resulting graph. Although this might seem like a small change, it makes a big difference from an algorithmic perspective: While the MST problem can be solved in polynomial time (see [ 21 ] for a translation of the original paper by Borůvka), the Steiner tree problem is NP-hard [ 10 ] . This highlights that, while it is important to make simplifications and generalizations when formalizing and theoretically studying a problem, it is also crucial to study the different aspects relevant to applications. In this regard, compared to the MST problem, the Steiner tree problem is a much better formalization of the challenges appearing in many practical problems. However, it still fails to capture crucial aspects that appear in various applications. To illustrate this in an example, assume we want to compute a cable layout for a solar farm, connecting the solar panels (sources) to transformers (sinks) that feed the produced electricity into the power grid. This is usually done in a hierarchical fashion, where the Steiner vertices between the sources and the sinks represent different intermediate components that are used for monitoring, as safety precautions, or for bundling lower-level components (e.g., Y-connectors, (re)combiner boxes, inverters). While it makes sense to abstract from the specific components, it would be an oversimplification to ignore the fact that these components have capacities depending on their level in the hierarchy. Moreover, different edges in the resulting cable layout have to deal with different amounts of current. As higher-capacity cables are more expensive, the cost of an edge not only depends on its length but also on the number of sources it connects to a sink. This changes the cost of an edge from a local property that is determined by just the edge alone to a global property that depends on the topology of the network. From an algorithmic standpoint, this seems to be a crucial difference. We note that the above mentioned shortcomings are not exclusive to computing cable layouts of solar farms. Other prominent examples of inherently hierarchical networks are health care systems [ 22 ] and production-distribution systems [ 11 ] ; also see the survey by Şahin and Süral on hierarchical facility location [ 3 ] . Motivated by the hierarchical cabling layout of solar farms, Gritzbach, Stampa and Wolf [ 8 ] considered multiple layers with capacity-constrained components and defined a cable cost function that depends on the amount of current that runs through a cable. However, the main difference to FLaMECaST is that candidate positions for the components are specified in the input. In fact, we are not aware of work on such variants where the Steiner vertices can be placed arbitrarily in the plane. Table 1: Comparison of the related problems Discrete Facility Location (DFL), Continuous Facility Location (CFL), Multi-Sink-Multi-Source Steiner Tree (MSMSST), Hop-Constrained Steiner Tree (HCST), Gilbert Arborescence Problem (GAP) and Solar Farm Cabling Layout Problem (SoFaCLaP). For DFL and CFL, we list some variants that have been researched. Problem Layers Positions Capacities Cost Function DFL [ 5 ] – none – k [ 3 ] discrete – uncapacitated – per facility [ 13 ] – per facility, per connection – concave per facility [ 23 ] CFL [ 17 ] – none – k [ 20 ] \mathbb{R}^{2} – uncapacitated – for all facilities [ 1 ] per facility, edge lengths MSMSST [ 28 ] unlimited \mathbb{R}^{2} — edge lengths HCST [ 27 ] k discrete — edge weights GAP [ 26 ] unlimited \mathbb{R}^{2} — \sum\len(e)\cdot(d+h\cdot\mathrm{flow}(e)^{\alpha} ) SoFaCLaP [ 8 ] k discrete per layer \sum\len(e)\cdot\mathrm{flow}(e) FLaMECaST k \mathbb{R}^{2} per layer \sum\len(e)\cdot\mathrm{flow}(e)^{\alpha} An overview of other problems that incorporate various aspects of FLaMECaST is presented in \cref tab:related_work. In the most unconstrained variant of FLaMECaST with arbitrarily many uncapacitated intermediate layers and \alpha=0 , it is closely related to the directed Steiner tree problem [ 29 ] , where the goal is to connect given sources to a specified sink with minimal cost. A variant of the Steiner tree problem that allows for multiple sinks is the Multi-Source-Multi-Sink Steiner tree problem [ 28 ] . Most Steiner tree problems in the Euclidean plane use the sum of edge lengths as cost; see the survey by Ljubić [ 16 ] . However, a Steiner tree variant called Gilbert Arborescence Problem uses a cost function that additionally depends on the weighted flow of an edge [ 26 ] , similar to FLaMECaST. A crucial difference of all Euclidean Steiner tree variants to FLaMECaST is that they do not allow a layered structure and capacitated Steiner vertices. A problem that extends to hierarchical structures more easily is the facility location problem, where the location for facilities