In this paper, we study the Distributed Maximization problem in the number-in-hand coordinator model. In this model, a central coordinator communicates with k sites, each of which holds a private integer, and the task of the coordinator is to output the maximum number among these integers. We propose two randomized algorithms to solve this problem effectively, achieving communication complexity of \(O(k\log \log N+ \log N)\) bits. In addition, we provide a tight lower bound which shows the optimality of our algorithms.

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

The Communication Complexity of Distributed Maximization

  • Yuxiang Tian,
  • Xiaoyi Zhu,
  • Zengfeng Huang

摘要

In this paper, we study the Distributed Maximization problem in the number-in-hand coordinator model. In this model, a central coordinator communicates with k sites, each of which holds a private integer, and the task of the coordinator is to output the maximum number among these integers. We propose two randomized algorithms to solve this problem effectively, achieving communication complexity of \(O(k\log \log N+ \log N)\) bits. In addition, we provide a tight lower bound which shows the optimality of our algorithms.