Hierarchical Clustering trees have been widely accepted as a useful form of
clustering data, resulting in a prevalence of adopting fields including
phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta
(STOC 16') initiated the analysis of these types of algorithms through the
lenses of approximation. Later, the dual problem was considered by Moseley and
Wang (NIPS 17') dubbing it the Revenue goal function. In this problem, given a
nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the
objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the
function $\sum_{i<j \in [n]} w_{ij} (n -|T_{ij}|)$, where $|T_{ij}|$ is the
number of leaves in the subtree rooted at the least common ancestor of $i$ and
$j$.
In our work we consider the revenue goal function and prove the following
results. First, we prove the existence of a bisection (i.e., a tree of depth 2
in which the root has two children, each being a parent of $n/2$ leaves) which
approximates the general optimal tree solution up to a factor of $\frac{1}{2}$
(which is tight). Second, we apply this result in order to prove a
$\frac{2}{3}p$ approximation for the general revenue problem, where $p$ is
defined as the approximation ratio of the Max-Uncut Bisection problem. Since
$p$ is known to be at least 0.8776 (Wu et al., 2015, Austrin et al., 2016), we
get a 0.585 approximation algorithm for the revenue problem. This improves a
sequence of earlier results which culminated in an 0.4246-approximation
guarantee (Ahmadian et al., 2019).

本研究考虑采用收益目标函数的双重问题，并证明了存在一种双重算法（经过半切）的近似解，得到了广义收益问题的 0.585 近似算法，从而改进了此前由一系列早期研究导致的 0.4246 近似保证。