Loading...
Please wait, while we are loading the content...
Similar Documents
On the Midpath Tree Conjecture: A Counter-Example (2001)
| Content Provider | CiteSeerX |
|---|---|
| Author | Martin, Rahul Shah Farach-Colton, Martin |
| Description | Introduction. Clustering data based on pairwise distances is a fundamental problem. Weighted trees can be used to represent hierarchical clusters. Multidimensional Scaling (MDS), in some formulations, is the problem of clustering data based on preserving their relative (rather than absolute) distances. We call this an ordinal clustering. A particular instance of this problem has been considered in the algorithmic computational biology community [KW, KHM]: Given a (total or partial) order on the pairwise distances between points, give a weighted tree on those points so that the pairwise pathlengths between points in the tree satisfies this order. This is, therefore, simply the MDS problem for hierarchical clustering, and we will refer to it as the HMDS problem. It has been conjectured [Kan] that there is a polynomial time algorithm to solve the HMDS problem, both while preserving the total order of the points, as well as while relaxing the order In proceedings of Symposium on Discrete Algorithms (SODA |
| File Format | |
| Language | English |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Pairwise Distance Md Problem Algorithmic Computational Biology Community Kw Hierarchical Cluster Midpath Tree Conjecture Total Order Multidimensional Scaling Particular Instance Pairwise Pathlengths Weighted Tree Fundamental Problem Ordinal Clustering Hierarchical Clustering Hmds Problem Polynomial Time Algorithm |
| Content Type | Text |
| Resource Type | Article |
