Approximating k-hop minimum-spanning trees

被引：34

作者：

Althaus, E

Funke, S

Har-Peled, S

Könemann, J

Ramos, EA

Skutella, M

机构：

[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany

[2] Univ Henri Poincare, LORIA, F-54506 Vandoeuvre Les Nancy, France

[3] Univ Illinois, Chicago, IL 60680 USA

[4] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 02期

关键词：

approximation algorithms; minimum spanning trees; depth restriction; metric space approximation;

D O I：

10.1016/j.orl.2004.05.005

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most k edges. We present an algorithm that computes such a tree of total expected cost O(log n) times that of a minimum-cost k-hop spanning-tree. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：115 / 120

页数：6

共 16 条

[1] A 3-approximation algorithm for the k-level uncapacitated facility location problem [J].

Aardal, K ;

Chudak, FA ;

Shmoys, DB .

INFORMATION PROCESSING LETTERS, 1999, 72 (5-6) :161-167

[2]

Alfandari L., 1999, International Transactions in Operational Research, V6, P607, DOI 10.1111/j.1475-3995.1999.tb00176.x

[3] Generalized submodular cover problems and applications [J].

Bar-Ilan, J ;

Kortsarz, G ;

Peleg, D .

THEORETICAL COMPUTER SCIENCE, 2001, 250 (1-2) :179-200

[4]

Bartal Y., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P161, DOI 10.1145/276698.276725

[5] Probabilistic approximation of metric spaces and its algorithmic applications [J].

Bartal, Y .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :184-193

[6]

Deering S. E., 1994, P SIGCOMM

[7] MULTICAST ROUTING IN DATAGRAM INTERNETWORKS AND EXTENDED LANS [J].

DEERING, SE ;

CHERITON, DR .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1990, 8 (02) :85-110

[8] Network flow models for designing Diameter-Constrained Minimum-Spanning and Steiner trees [J].

Gouveia, L ;

Magnanti, TL .

NETWORKS, 2003, 41 (03) :159-173

[9] Greedy strikes back: Improved facility location algorithms [J].

Guha, S ;

Khuller, S .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01) :228-248

[10] Minimum spanning tree with hop restrictions [J].

Hassin, R ;

Levin, A .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 48 (01) :220-238

← 1 2 →