Bypassing Surface Embeddings: Approximation Schemes for Network Design in Minor-free Metrics
Abstract
Since the mid 90s, the study of the complexity of classic network design
problems such as the traveling salesman problem (TSP), the Steiner tree problem (ST),
or the $k$-MST problem on metric spaces such as low-dimensional Euclidean spaces,
doubling metrics, planar or minor-free metrics,
has led to major improvements of our understanding
of the structure of both these important metric spaces, and the underlying problems.
In their celebrated work, Arora and Mitchell gave quasi-polynomial-time approximation schemes (QPTAS)
for several network design problems in Euclidean space, that have later been improved
to polynomial and (near-)linear in some cases. Arora and Mitchell's QPTAS result has been
extended by Talwar [STOC'04] to doubling metrics showing that the Euclidean embedding
is not a necessary condition to design approximation schemes for network design problems.
In the case of planar metrics, the picture is already less satisfactory: The first
approximation schemes for Steiner tree only dates back to [] and nothing better than the general
case is known for $k$-MST, an open question that has thus been repeatedly asked.
Even when approximation schemes are known for the planar case, generalizing them to the minor-free
setting is often a major challenge because most of the topological properties are lost.
In this case, one of the most important question of the field is whether
we bypass these topological arguments to obtain a general framework for network
design problems in minor-free metrics?
In this paper, we answer by the affirmative by proposing a framework for network design
problems in minor-free metrics.
We give the first approximation schemes, with quasi-polynomial running time,
for $k$-MST, Steiner tree, Steiner forest, Prize-collecting Steiner tree in minor-free metrics.
The result on $k$-MST was not known before even for the planar case, while Steiner tree on
minor-free metrics has been one of the major challenge. Here we also obtain approximation
schmes for the two non-trivial generalizations Steiner forest and Prize-collecting Steiner tree.
problems such as the traveling salesman problem (TSP), the Steiner tree problem (ST),
or the $k$-MST problem on metric spaces such as low-dimensional Euclidean spaces,
doubling metrics, planar or minor-free metrics,
has led to major improvements of our understanding
of the structure of both these important metric spaces, and the underlying problems.
In their celebrated work, Arora and Mitchell gave quasi-polynomial-time approximation schemes (QPTAS)
for several network design problems in Euclidean space, that have later been improved
to polynomial and (near-)linear in some cases. Arora and Mitchell's QPTAS result has been
extended by Talwar [STOC'04] to doubling metrics showing that the Euclidean embedding
is not a necessary condition to design approximation schemes for network design problems.
In the case of planar metrics, the picture is already less satisfactory: The first
approximation schemes for Steiner tree only dates back to [] and nothing better than the general
case is known for $k$-MST, an open question that has thus been repeatedly asked.
Even when approximation schemes are known for the planar case, generalizing them to the minor-free
setting is often a major challenge because most of the topological properties are lost.
In this case, one of the most important question of the field is whether
we bypass these topological arguments to obtain a general framework for network
design problems in minor-free metrics?
In this paper, we answer by the affirmative by proposing a framework for network design
problems in minor-free metrics.
We give the first approximation schemes, with quasi-polynomial running time,
for $k$-MST, Steiner tree, Steiner forest, Prize-collecting Steiner tree in minor-free metrics.
The result on $k$-MST was not known before even for the planar case, while Steiner tree on
minor-free metrics has been one of the major challenge. Here we also obtain approximation
schmes for the two non-trivial generalizations Steiner forest and Prize-collecting Steiner tree.
Research Areas
