A Caltech Library Service

Approximation algorithms for labeling hierarchical taxonomies

Rabani, Yuval and Schulman, Leonard J. and Swamy, Chaitanya (2008) Approximation algorithms for labeling hierarchical taxonomies. In: SODA '08 Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. SIAM , Philadelphia, PA, pp. 671-680.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the following taxonomy labeling problem. Each node of an n-node tree has to be labeled with the values of k attributes. A partial labeling is given as part of the input. The goal is to complete this labeling, minimizing the maximum variation in labeling along an edge. A special case of this problem (which we call the label extension problem), where every node is either completely labeled or not labeled at all, has been considered previously. We present an O(log^2 k)-approximation algorithm based on a natural linear programming relaxation. Our results reduce the taxonomy labeling problem to another problem we introduce, called the multicut packing problem (on trees): given k multicommodity flow instances, find a multicut for each instance so as to minimize the maximum number of multicuts that use any single edge. Our algorithm yields an O(log^2 k)-approximation algorithm for this more general problem. We show that the integrality gap of our relaxation is Ω(log k), even when applied to the taxonomy labeling problem with 0-1 labels. For the label extension problem, we considerably improve the previous O(log n) approximation guarantee and give the first constant-factor approximation algorithm for this problem. Our work relies on relating the label extension problem to questions on Lipschitz extensions of functions into Banach spaces. In particular, our approximation algorithm builds upon Matoušek's tree metrics extension theorem. Our algorithm also works for other metrics on the label-set, such as edit distance with unit-cost operations, and more generally any shortest path metric induced by an unweighted graph.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2008 SIAM. Supported in part by ISF 52/03, BSF 2002282, and the Fund for the Promotion of Research at the Technion. Supported in part by NSF CCF-0515342, NSA H98230-06-1-0074, and NSF ITR CCR-0326554. Research supported partially by NSERC grant 32760-06.
Funding AgencyGrant Number
Israel Science Foundation52/03
Binational Science Foundation (USA-Israel)2002282
Fund for the Promotion of Research at the TechnionUNSPECIFIED
National Security AgencyH98230-06-1-0074
Natural Sciences and Engineering Research Council of Canada (NSERC)32760-06
Record Number:CaltechAUTHORS:20161212-164128630
Persistent URL:
Official Citation:Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. 2008. Approximation algorithms for labeling hierarchical taxonomies. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 671-680.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72748
Deposited On:13 Dec 2016 02:28
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page