Divide-and-conquer approximation algorithms via spreading metrics

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

Research output: Contribution to journalConference articlepeer-review

52 Scopus citations

Abstract

A novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems is presented. The paradigm models graph optimization problems that satisfy two properties. First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimization problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound on the cost of solving the optimization problem.

Original languageEnglish (US)
Pages (from-to)62-71
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA
Duration: Oct 23 1995Oct 25 1995

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Divide-and-conquer approximation algorithms via spreading metrics'. Together they form a unique fingerprint.

Cite this