RATES OF CONVERGENCE FOR QUASI-ADDITIVE SMOOTH EUCLIDEAN FUNCTIONALS AND APPLICATION TO COMBINATORIAL OPTIMIZATION PROBLEMS

被引：3

作者：

JAILLET, P

机构：

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1992年 / 17卷 / 04期

关键词：

EUCLIDEAN FUNCTIONALS; STOCHASTIC; CONVERGENCE RATES;

D O I：

10.1287/moor.17.4.964

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Rates of convergence of limit theorems are established for a class of random processes called here quasi-additive smooth Euclidean functionals. Examples include the objective functions of the traveling salesman problem, the Steiner tree problem, the minimum spanning tree problem, the minimum weight matching problem, and a variant of the minimum spanning tree problem with power weighted edges.

引用

页码：964 / 980

页数：17

共 13 条

[1]

[Anonymous], 1955, AM MATH MON, DOI [10.2307/2308012, DOI 10.2307/2308012]

[2]

Beardwood J, 1959, P CAMBRIDGE PHILOS S, V55, P299, DOI [DOI 10.1017/S0305004100034095, 10.1017/S0305004100034095]

[3]

Few L., 1955, MATHEMATIKA, V2, P141

[4] PROBABILISTIC ANALYSIS OF THE HELD AND KARP LOWER BOUND FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM [J].

GOEMANS, MX ;

BERTSIMAS, DJ .

MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (01) :72-89

[5]

HALFIN S, 1990, COMMUNICATION

[6]

JAILLET P, IN PRESS MATH OPER R

[7]

Karp R. M., 1977, Mathematics of Operations Research, V2, P209, DOI 10.1287/moor.2.3.209

[8]

MORAN S, 1982, 235 COMP SCI DEP TEC

[9]

RHEE W, 1988, ANN PROBAB, V17, P1

[10] MARTINGALE INEQUALITIES AND NP-COMPLETE PROBLEMS [J].

RHEE, WT ;

TALAGRAND, M .

MATHEMATICS OF OPERATIONS RESEARCH, 1987, 12 (01) :177-181

← 1 2 →