Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.20041 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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.