Approximation algorithms for routing and scheduling problems on networks

网络路由和调度问题的近似算法

• 批准号: 23500023
• 负责人: ASANO Takao
• 金额: $ 3.24万
• 依托单位: Chuo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500023/
• 关键词: 近似保証アルゴリズム; ネットワーク; ルーティング; スケジューリング; ラウンディング; ユニークゲーム予想; 組合せオークション; ナッシュ均衡; 情報検索

We considered routing and scheduling problems on a network as a combinatorial auction problem for maximizing the social welfare of all participants on the network and investigated the existence of a stable solution (Nash equilibrium) which all participants agree on. We gave a characterization for the existence of a Nash equilibrium in such a combinatorial auction when valuations by all participants satisfy symmetric and subadditive properties. By this characterization, we obtained an algorithm for deciding a Nash equilibrium exists. Furthermore, we showed that, if valuations by all participants satisfy symmetric and submodular properties, Nash equilibrium always exists and we can find such a Nash equilibrium in polynomial time.

我们将网络上的路由和调度问题视为一个组合拍卖问题，用于最大程度地提高网络上所有参与者的社会福利，并研究了所有参与者都同意的稳定解决方案（NASH平衡）的存在。当所有参与者的估值满足对称性和亚addivity属性时，我们为在这种组合拍卖中存在NASH平衡的表征提供了表征。通过这种表征，我们获得了一种用于确定NASH平衡的算法。此外，我们表明，如果所有参与者的估值都满足对称和下型特性，则NASH平衡始终存在，并且我们可以在多项式时间内找到这种NASH平衡。

项目成果

近似アルゴリズム( V.V. Vazirani : Approximation Algorithms, Springer, 2002 の日本語訳)

近似算法（V.V. Vazirani 的日文翻译：近似算法，Springer，2002 年）

• 发表时间: 2012
• 作者: Shuji Takahashi;Kenta Sakawa;Yoichi Shiraishi and Hiroshi Miyashita;江藤宏;浅野孝夫
• 通讯作者: 浅野孝夫

Mining and Explaining Relationships in Wikipedia

挖掘和解释维基百科中的关系

• 发表时间: 2012
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: Xinpeng Zhang;Yasuhito Asano and Masatoshi Yoshikawa
• 通讯作者: Yasuhito Asano and Masatoshi Yoshikawa

組合せ最適化第2 版 - 理論とアルゴリズム( B. Korte, J. Vygen: Combinatorial Optimization - Theory and Algorithms, 2008 の日本語訳)

组合优化第二版 - 理论和算法（B. Korte、J. Vygen 的日文翻译：组合优化 - 理论和算法，2008 年）

• 发表时间: 2012
• 作者: 浅野孝夫;浅野泰仁;小野孝男;平田富夫
• 通讯作者: 平田富夫

Ranking Content-Based Social Image Search Results with Social Tags

使用社交标签对基于内容的社交图像搜索结果进行排名

• 发表时间: 2011
• 作者: Jiyi Li;Qiang Ma;Yasuhito Asano;Masatoshi Yoshikawa
• 通讯作者: Masatoshi Yoshikawa

ネットワーク・大衆・マーケット --- 現代社会の複雑な連結性についての推論（原著：D. Easley and J. Kleinberg, Networs, Crowds, and Markets, Cambridge, 2010の翻訳）

网络、人群和市场 --- 现代社会复杂连通性的推理（译自 D. Easley 和 J. Kleinberg，《网络、人群和市场》，剑桥，2010 年）

• 发表时间: 2013
• 作者: 浅野孝夫;浅野泰仁
• 通讯作者: 浅野泰仁