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
    GOEMANS, MX
    BERTSIMAS, DJ
    [J]. 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
    RHEE, WT
    TALAGRAND, M
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1987, 12 (01) : 177 - 181
12