Designing Approximate Binary Trees for Trees
arXiv:2604.20786
Abstract
We study the following problem that is motivated by demand-aware network design: Given a tree~, the task is to find a binary tree~ on the same vertex set. The objective is to minimize the sum of distances in~ between vertex pairs that are adjacent in~. We present a linear-time factor-4 approximation for this problem.