Approximation methods improve building binary trees from general trees
From Trees to Binary Trees: Approximation Algorithms and a PTAS
Data Structures and Algorithms
Summary
The paper addresses how to convert a given tree structure into a binary tree that keeps the same nodes but arranges them so distances between connected nodes stay as short as possible. The authors improve previous work by providing a straightforward algorithm that quickly finds a solution within about 2.67 times the optimal distance sum. They also present a more complex method that can get arbitrarily close to the best possible solution when extra nodes (Steiner nodes) are allowed. Their approach breaks down the tree into parts, solves each, and then combines these solutions.
What this means in practice
- •For network designers: Design binary network topologies from existing tree-like layouts while minimizing communication distances between nodes.
- •For database engineers: Optimize hierarchical data structures by approximating minimal-distance binary trees that maintain original data nodes with optional helper nodes.
Authors
Fabian Weisbrodt, Florian Werner
Abstract
Kellerhals, Krebs, Nichterlein, and Schmid introduced the optimization problem Tree in Binary Tree (TBT), where, given a tree $T$, the task is to find a binary tree $S^*$ with $V(T)=V(S^*)$ that minimizes $\sum_{uv\in E(T)} \operatorname{dist}_{S^*}(u,v)$. They also introduced the variant Tree in Binary Tree With Steiner Nodes (TBT-SN), where the condition $V(T)=V(S^*)$ is relaxed to $V(T)\subseteq V(S^*)$. We give a simple linear-time $\frac{8}{3}$-approximation algorithm for TBT and a polynomial-time approximation scheme (PTAS) for TBT-SN. Our main building idea in both algorithms is to iteratively consider subtrees of the tree $T$ which contain all vertices below some vertex $v$ and construct a solution where $v$ has degree 1. For the PTAS, we cut $T$ into smaller trees, solve these instances, modify the obtained solutions, and combine them to achieve a solution for the original instance.