Scholarlink

Motivated by the online optimization problems in the random order model, we propose novel generalized concentration bounds such as Chernoff bounds, Hoeffding bounds, and Bernstein bounds for general random variables. We then initiate the study of the online resource allocation with concave returns (ORACR) problem. Based on the new bounds, we propose an algorithm for ORACR that achieves near-optimal performance where the inputs arrive in uniformly random order under almost tight conditions. Based on these novel concentration bounds, we obtain an improved condition for the near-optimal performance of the AdWords problem with concave returns (APCR).

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

New Concentration Bounds and Their Applications in Online Resource Allocation

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Jinshan Zhang,
  • Biaoshuai Tao,
  • Nan Zhao,
  • Meng Xi,
  • Tao Jin,
  • Jianwei Yin

摘要

Motivated by the online optimization problems in the random order model, we propose novel generalized concentration bounds such as Chernoff bounds, Hoeffding bounds, and Bernstein bounds for general random variables. We then initiate the study of the online resource allocation with concave returns (ORACR) problem. Based on the new bounds, we propose an algorithm for ORACR that achieves near-optimal performance where the inputs arrive in uniformly random order under almost tight conditions. Based on these novel concentration bounds, we obtain an improved condition for the near-optimal performance of the AdWords problem with concave returns (APCR).