On the price of stability for designing undirected networks with fair cost allocations
On the price of stability for designing undirected networks with fair cost allocations
复制标题
DOI：
10.1007/11786986_53
复制
发表时间：
2006-01-01
期刊：
影响因子：
--
通讯作者：
Shabo, Ronen
中科院分区：
文献类型：
--
作者：
Fiat, Amos;Kaplan, Haim;Shabo, Ronen
本文讨论了文献[1]中提出的无向图的公平费用分配网络设计的稳定性代价的边界问题。我们考虑的情况下，有一个代理在每个顶点。我们证明了稳定性的代价是O（log log n）。我们证明了这一点，通过定义一个特定的改进动态相关图。这种证明技术可能有其他的应用，是独立的利益。
In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. We consider the case where there is an agent in every vertex. We show that the price of stability is O(log log n). We prove this by defining a particular improving dynamics in a related graph. This proof technique may have other applications and is of independent interest.