Near-optimal bounded-degree spanning trees

J. C. Hansen, E. Schmutz

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Random costs C(i, j) are assigned to the arcs of a complete directed graph on n labeled vertices. Given the cost matrix Cn = (C(i, J)), let Tk* = Tk*(Cn) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal to k. Since it is NP-hard to find Tk*, we instead consider an efficient algorithm that finds a near-optimal spanning tree Tka. If the edge costs are independent, with a common exponential(1) distribution, then, as n ? 8, E(Cost(Tka) = E(Cost(Tk*) + o(1). Upper and lower bounds for E(Cost(Tk*)) are also obtained for k = 2.

Original languageEnglish
Pages (from-to)148-180
Number of pages33
JournalAlgorithmica
Volume29
Issue number1-2
Publication statusPublished - Jan 2001

Keywords

  • Approximation algorithm
  • Assignment problem
  • Random mapping
  • Spanning tree

Fingerprint Dive into the research topics of 'Near-optimal bounded-degree spanning trees'. Together they form a unique fingerprint.

Cite this