English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-D531-C Version Permalink: https://hdl.handle.net/21.11116/0000-0005-3424-8
Genre: Conference Paper

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: Issued
 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