Worst case asymptotics of power-weighted euclidean functionals

Sungchul Lee

doi:10.1016/S0012-365X(01)00437-X

Worst case asymptotics of power-weighted euclidean functionals

Sungchul Lee

Department of Mathematics

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

2 Citations (Scopus)

Abstract

Let || ≤ n, be a subset of [0,1]^d, and let L(,[0,1]^d,p) be the length of the minimal matching, the minimal spanning tree, or the traveling salesman problem on with weight function w(e) = |e|^p. In the case 1 ≤ p < d, Yukich (Combinatorica 16 (1996) 575) obtained the asymptotic of α_L (n,d,p) = max_{⊃[0,1]d,[]≤n} L(,[0,1]^d,p). In this paper we extend his result to the whole range 0 < p < ∞.

Original language	English
Pages (from-to)	291-300
Number of pages	10
Journal	Discrete Mathematics
Volume	256
Issue number	1-2
DOIs	https://doi.org/10.1016/S0012-365X(01)00437-X
Publication status	Published - 2002 Sept 28

Bibliographical note

Funding Information:
This work was supported by grant No. 1999-2-0577 from the interdisciplinary research program of the KOSEF, Com2MaC in POSTECH, and the BK21 project of the Department of Mathematics, Yonsei University. E-mail address: sungchul@mail.yonsei.ac.kr (S. Lee).

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(01)00437-X

Cite this

@article{85ecba6b720c4a45b369660e0e21ac6b,

title = "Worst case asymptotics of power-weighted euclidean functionals",

abstract = "Let || ≤ n, be a subset of [0,1]d, and let L(,[0,1]d,p) be the length of the minimal matching, the minimal spanning tree, or the traveling salesman problem on with weight function w(e) = |e|p. In the case 1 ≤ p < d, Yukich (Combinatorica 16 (1996) 575) obtained the asymptotic of αL (n,d,p) = max⊃[0,1]d,[]≤n L(,[0,1]d,p). In this paper we extend his result to the whole range 0 < p < ∞.",

author = "Sungchul Lee",

note = "Funding Information: This work was supported by grant No. 1999-2-0577 from the interdisciplinary research program of the KOSEF, Com2MaC in POSTECH, and the BK21 project of the Department of Mathematics, Yonsei University. E-mail address: sungchul@mail.yonsei.ac.kr (S. Lee).",

year = "2002",

month = sep,

day = "28",

doi = "10.1016/S0012-365X(01)00437-X",

language = "English",

volume = "256",

pages = "291--300",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

T1 - Worst case asymptotics of power-weighted euclidean functionals

AU - Lee, Sungchul

N1 - Funding Information: This work was supported by grant No. 1999-2-0577 from the interdisciplinary research program of the KOSEF, Com2MaC in POSTECH, and the BK21 project of the Department of Mathematics, Yonsei University. E-mail address: sungchul@mail.yonsei.ac.kr (S. Lee).

PY - 2002/9/28

Y1 - 2002/9/28

N2 - Let || ≤ n, be a subset of [0,1]d, and let L(,[0,1]d,p) be the length of the minimal matching, the minimal spanning tree, or the traveling salesman problem on with weight function w(e) = |e|p. In the case 1 ≤ p < d, Yukich (Combinatorica 16 (1996) 575) obtained the asymptotic of αL (n,d,p) = max⊃[0,1]d,[]≤n L(,[0,1]d,p). In this paper we extend his result to the whole range 0 < p < ∞.

AB - Let || ≤ n, be a subset of [0,1]d, and let L(,[0,1]d,p) be the length of the minimal matching, the minimal spanning tree, or the traveling salesman problem on with weight function w(e) = |e|p. In the case 1 ≤ p < d, Yukich (Combinatorica 16 (1996) 575) obtained the asymptotic of αL (n,d,p) = max⊃[0,1]d,[]≤n L(,[0,1]d,p). In this paper we extend his result to the whole range 0 < p < ∞.

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

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

U2 - 10.1016/S0012-365X(01)00437-X

DO - 10.1016/S0012-365X(01)00437-X

M3 - Article

AN - SCOPUS:33645774516

SN - 0012-365X

VL - 256

SP - 291

EP - 300

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-2

ER -

Worst case asymptotics of power-weighted euclidean functionals

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this