# Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees

arXiv: https://arxiv.org/abs/2402.05560 · HTML: https://mlsanity.com/paper/2402.05560/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2024.

## Built on by (most cited first, 1 of 1)

- [Precedence-Constrained Decision Trees and Coverings](https://mlsanity.com/paper/2602.21312/) (2026)

## Abstract (arXiv)

The graph invariant EPT-sum has cropped up in several unrelated fields in later years: As an objective function for hierarchical clustering, as a more fine-grained version of the classical edge ranking problem, and, specifically when the input is a vertex-weighted tree, as a measure of average/expected search length in a partially ordered set. The EPT-sum of a graph G is defined as the minimum sum of the depth of every leaf in an edge partition tree (EPT), a rooted tree where leaves correspond to vertices in G and internal nodes correspond to edges in G. A simple algorithm that approximates EPT-sum on trees is given by recursively choosing the most balanced edge in the input tree G to build an EPT of G. Due to its fast runtime, this balanced cut algorithm can be used in practice, and has earlier been analysed to give a 1.62-approximation on trees. In this paper, we show that the balanced cut algorithm gives a 1.5-approximation of EPT-sum on trees, which amounts to a tight analysis and answers a question posed by Cicalese et al. in 2014.