Near-optimal bounded-degree spanning trees

J. C. Hansen; E. Schmutz

Near-optimal bounded-degree spanning trees

Research output: Contribution to journal › Article › peer-review

Abstract

Random costs C(i, j) are assigned to the arcs of a complete directed graph on n labeled vertices. Given the cost matrix C_n = (C(i, J)), let T_k* = T_k*(C_n) 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 T_k*, we instead consider an efficient algorithm that finds a near-optimal spanning tree T_k^a. If the edge costs are independent, with a common exponential(1) distribution, then, as n ? 8, E(Cost(T_k^a) = E(Cost(T_k*) + o(1). Upper and lower bounds for E(Cost(T_k*)) are also obtained for k = 2.

Original language	English
Pages (from-to)	148-180
Number of pages	33
Journal	Algorithmica
Volume	29
Issue number	1-2
Publication status	Published - Jan 2001

Keywords

Approximation algorithm
Assignment problem
Random mapping
Spanning tree

Cite this

@article{e4a5a731a6594455a9a77fe4ee153756,

title = "Near-optimal bounded-degree spanning trees",

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.",

keywords = "Approximation algorithm, Assignment problem, Random mapping, Spanning tree",

author = "Hansen, {J. C.} and E. Schmutz",

year = "2001",

month = jan,

language = "English",

volume = "29",

pages = "148--180",

journal = "Algorithmica ",

issn = "1432-0541",

publisher = "Springer",

number = "1-2",

}

TY - JOUR

T1 - Near-optimal bounded-degree spanning trees

AU - Hansen, J. C.

AU - Schmutz, E.

PY - 2001/1

Y1 - 2001/1

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Assignment problem

KW - Random mapping

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=0013333371&partnerID=8YFLogxK

M3 - Article

SN - 1432-0541

VL - 29

SP - 148

EP - 180

JO - Algorithmica

JF - Algorithmica

IS - 1-2

ER -

Near-optimal bounded-degree spanning trees

Abstract

Keywords

Other files and links

Fingerprint

Cite this