期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

由均匀染色导出的强Chernoff界（英文） 被引量：1

A STRONG CHERNOFF BOUNDS DERIVED FROM EQUITABLE COLORINGS OF GRAPHS
下载PDF
导出
摘要 本文研究了相关变量的Chernoff问题.利用相关变量构造图的方法,利用均匀染色的结果,获得了更强的Chernoff界,推广了Chernoff不等式在相关随机变量的不等式下的界. In this paper, we present a strong Chernoff bounds by using the existence of smallsized equitable colorings of graphs. The case we considered here is for sums of random variableswith dependence. Our result improves the known results as far as we known.
作者 王涛 刘明菊 李德明
机构地区 华北科技学院基础部 北京航空航天大学数学与系统科学学院 首都师范大学数学科学学院
出处 《数学杂志》 CSCD 北大核心 2014年第6期1015-1024,共10页 Journal of Mathematics
基金 Supported by National Natural Science Foundation of China(11371052 11271267 10971144 11101020) NSCFBJ(1102015) the Fundamental Research Funds for the Central Universities(2011B019 3142013104) North China Institute of Science And Technology Key Discipline Items of Basic Construction(HKXJZD201402)
关键词 均匀染色 相关图 Chernoff界 coloring dependence graph Chernoff bounds
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献10

  • 1Alon N, Spencer J H. The probabilistic method (3rd edition) [M]. New York: Wiley, 2007.
  • 2Bollobas B, Guy R K. Equitable and proportional coloring of trees [J]. J. Combinatorial Theory, Series B, 1983,34(2): 177-186.
  • 3Chernoff H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations [J]. Annals of Mathematical Statistics, 1952,23(2): 493-507.
  • 4Hajnal H, Szemeredi S. Proof of a conjecture of erdos[A]. Paul. Erdos, A. Renyi, and V.T. Sos, editors, Combinatorial Theory and Its Applications[C]. Vol II, Volume 4 of Colloquia Mathematica Societatis Janos Bolyai, North-Holland, 1970: 601-623.
  • 5Motwani R, Raghavan P. Randomized algorithms [M]. Cambridge: Cambridge University Press, 1995.
  • 6Panconesi A, Srinivasan A. Randomized distributed edge colouring via an extension of the Chernoff-Hoeffding bounds [J]. SIAM J. on Computing, 1997, 26(2): 350-368.
  • 7Pemmaraju S V. Equitable coloring extents Chernoff-Hoeffding bounds [A]. Pemmaraju S V. Approx-Random 2001 [C]. LNCS 2129,2001: 285-296.
  • 8Pemmaraju S V. Equitable colorings, proportional colorings, and Chernoff-Hoeffding bounds [A]. Technical report, TR 01-05, Department of Computer Science, The University of Iowa, 2001.
  • 9Schmidt J, Siegel A, Srinivasan A. Chernoff-Hoeffding bounds For applications with limited independence [J]. SIAM J. Discrete Mathmatics, 1995, 8(2): 223—250.
  • 10Spencer J. Ten lectures on the probabilistic method [M]. Philadelphia: SIAM, 1987.

引证文献1

二级引证文献7

数学杂志
2014年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部