Where's the winner? Max-finding and sorting with metric costs

Anupam Gupta, Amit Kumar

Research output: Contribution to journalConference articlepeer-review

Abstract

Traditionally, a fundamental assumption in evaluating the performance of algorithms for sorting and selection has been that comparing any two elements costs one unit (of time, work, etc.); the goal of an algorithm is to minimize the total cost incurred. However, a body of recent work has attempted to find ways to weaken this assumption - in particular, new algorithms have been given for these basic problems of searching, sorting and selection, when comparisons between different pairs of elements have different associated costs. In this paper, we further these investigations, and address the questions of max-finding and sorting when the comparison costs form a metric; i.e., the comparison costs cuv respect the triangle inequality cvw + cuw ≥ cuw for all input elements u, v and w. We give the first results for these problems - specifically, we present - An O(log n)-competitive algorithm for max-finding on general metrics, and we improve on this result to obtain an O(1)-competitive algorithm for the max-finding problem in constant dimensional spaces. - An O(log2 n)-competitive algorithm for sorting in general metric spaces. Our main technique for max-finding is to run two copies of a simple natural online algorithm (that costs too much when run by itself) in parallel. By judiciously exchanging information between the two copies, we can bound the cost incurred by the algorithm; we believe that this technique may have other applications to online algorithms.

Original languageEnglish (US)
Pages (from-to)74-85
Number of pages12
JournalLecture Notes in Computer Science
Volume3624
DOIs
StatePublished - 2005
Event8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005 - Berkeley, CA, United States
Duration: Aug 22 2005Aug 24 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Where's the winner? Max-finding and sorting with metric costs'. Together they form a unique fingerprint.

Cite this