Stability vs.Optimality in Selfish Ring Routing

来源 :Acta Mathematica Sinica(English Series) | 被引量 : 0次 | 上传用户:xnf0769
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We show that there exists an optimal solution that is a 9-approximate Nash equilibrium, significantly improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436. We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We show that there exists an optimal solution that is a 9-approximate Nash equilibrium, substantially improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436.
其他文献
十年来,亚太集团从一个濒临倒闭的局面发展为年销售额近3亿元的大型水工企业集团,这是他们实施人才战略、构筑人才高地的成功体现.近年来,该集团不仅加大了人才引进和培养的
为探究吕家坨井田地质构造格局,根据钻孔勘探资料,采用分形理论和趋势面分析方法,研究了井田7
为探究吕家坨井田地质构造格局,根据钻孔勘探资料,采用分形理论和趋势面分析方法,研究了井田7
为探究吕家坨井田地质构造格局,根据钻孔勘探资料,采用分形理论和趋势面分析方法,研究了井田7
讨论非线性方程F(λ,u)=0的分歧问题,这里F:R×X→Y为非线性微分映射,X,Y为Banach空间,利用Lyapunov-Schmidt约化过程和隐函数定理证得一个从多重特征值出发的分歧定理.推广
试析企业标准体系与质量保证体系的关系袁福敏(广东省江门柴油机总厂)国内外的成功经验证明,实施GB/T19000-ISO9000系列标准,建立健全质量保证体系,是在考虑风险、成本和利益的基础上使质量最佳化,并
智能建筑在当代建筑中的地位不断攀升,而建筑电气技术作为支持智能建筑的技术平台,其内容得以不断发展.本文介绍了建筑电气技术和智能建的概念,以及建筑电气技术在智能建筑领