English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Triangle Fixing Algorithms for the Metric Nearness Problem

Dhillon, I., Sra, S., & Tropp, J. (2005). Triangle Fixing Algorithms for the Metric Nearness Problem. In L. Saul, Y. Weiss, & L. Bottou (Eds.), Advances in Neural Information Processing Systems 17 (pp. 361-368). Cambridge, MA, USA: MIT Press.

Item is

Files

show Files

Creators

show
hide
 Creators:
Dhillon, I1, Author              
Sra, S1, Author              
Tropp, J, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Various problems in machine learning, databases, and statistics involve pairwise distances among a set of objects. It is often desirable for these distances to satisfy the properties of a metric, especially the triangle inequality. Applications where metric data is useful include clustering, classification, metric-based indexing, and approximation algorithms for various graph problems. This paper presents the Metric Nearness Problem: Given a dissimilarity matrix, find the "nearest" matrix of distances that satisfy the triangle inequalities. For lp nearness measures, this paper develops efficient triangle fixing algorithms that compute globally optimal solutions by exploiting the inherent structure of the problem. Empirically, the algorithms have time and storage costs that are linear in the number of triangle constraints. The methods can also be easily parallelized for additional speed.

Details

show
hide
Language(s):
 Dates: 2005-07
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: 5224
 Degree: -

Event

show
hide
Title: Eighteenth Annual Conference on Neural Information Processing Systems (NIPS 2004)
Place of Event: Vancouver, BC, Canada
Start-/End Date: 2004-12-13 - 2004-12-16

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advances in Neural Information Processing Systems 17
Source Genre: Proceedings
 Creator(s):
Saul, LK, Editor
Weiss, Y, Editor
Bottou, L, Editor
Affiliations:
-
Publ. Info: Cambridge, MA, USA : MIT Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 361 - 368 Identifier: ISBN: 0-262-19534-8