arXiv preprint ·
From Trees to Binary Trees: Approximation Algorithms and a PTAS
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Four-Coloring Planar Graphs in Linear Time
Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
Traveling Salesman Problem on Graphs with Proportional Independent Set
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
On $t$-designs supported by self-orthogonal codes
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.