Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
There are many classical optimization problems related to network design, e.g. see the survey by Magnanti & Wong @cite_1 . Many of them are NP-complete, e.g. all the problems labeled ND'' in @cite_39 . Our model is closely related to the Network Design Problem @cite_21 and the Optimum Communication Spanning Tree Problem (ND7 in @cite_39 ). In particular, finding the social optimum network corresponds to a variant of the Network Design Problem, where, instead of having separate budgets for buying edges and for the routing cost, the sum of edge costs and routing costs, i.e., the total distance between all pairs of nodes, is to be minimized. Hence we strongly suspect that computing the social optimum in all versions of our model, with the and the as exceptions, is NP-hard.
@cite_21 @cite_1 @cite_39
2623734410 2166747457 2022092881 2016218947
Consider the following classical network design problem: a set of terminals T = [t i wants to send traffic to a "root" r in an n-node graph G = (V,E). Each terminal t i sends d i units of traffic, and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity u e --- and hence provisioning k x u e bandwidth on edge e incurs a cost of [k] times the cost of that edge. The objective is a minimum-cost feasible solution.This is one of many network design problems widely studied where the bandwidth allocation being governed by side constraints: edges may only allow a subset of cables to be purchased on them, or certain quality-of-service requirements may have to be met.In this work, we show that the above problem, and in fact, several basic problems in this general network design framework, cannot be approximated better than Ω(log log n) unless NP ⊆ DTIME (nO(log log log n). In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem [7], (ii) the Cost-Distance problem [31], and the single-sink version of an even more fundamental problem, (iii) Fixed Charge Network Flow [33]. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first non-constant hardness results known for all these problems. Consider the following classical network design problem: a set of terminals T e ti wishes to send traffic to a root r in an n-node graph G e (V, E). Each terminal ti sends di units of traffic and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity ue and hence provisioning k × ue bandwidth on edge e incurs a cost of ⌈k⌉ times the cost of that edge. The objective is a minimum-cost feasible solution. This is one of many network design problems widely studied where the bandwidth allocation is governed by side constraints: edges can only allow a subset of cables to be purchased on them or certain quality-of-service requirements may have to be met. In this work, we show that this problem and, in fact, several basic problems in this general network design framework cannot be approximated better than Ω(log log n) unless NP ⊆ DTIME (nO(log log log n)), where vVv e n. In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the (single-sink) Cost-Distance problem, and (iii) the single-sink version of an even more fundamental problem, Fixed Charge Network Flow. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first nonconstant hardness results known for all these problems. We study the following network design problem: Given a communication network, find a minimum cost subset of missing links such that adding these links to the network makes every pair of points within distance at most d from each other. The problem has been studied earlier [17] under the assumption that all link costs as well as link lengths are identical, and was shown to be R(logn)-hard for every d 2 4. We present a novel linear programming based approach to obtain an O(log la log d) approximation algorithm for the case of uniform link lengths and costs. We also extend the Cl(Iogn) hardness to d E Z, 3). On the other hand, if link costs can vary, we show that the prob” ‘-’ n lem is n(Z s )hard for d > 3. This version of our problem can be viewed as a special case of the minimum cost d-spanner problem and thus our hardness result applies there as well. For d = 2, however, we show that the problem continues to be O(logn) approximable by giving an O(log n)-approximation to the more general minimum cost Z-spanner problem. An n(2”s’-’ “)-hardness result also holds when all link costs are identical but link lengths may vary (applies even when all lengths are 1 or 2). Our reduction from the label cower problem [3] also applies to another well-studied network design problem. We show that the directed genemlized steiner network problem [6] is n(2 I’&-’ “)-hard, significantly improving upon the Q(logn) hardness known prior to our work. We also present O(n log d) approximation algorithm for our problem under arbitrary link costs and polynomially bounded link lengths. Same result holds for the minimum cost d-spanner problem. Finally, all our positive results extend to the case where each pair (u,u) of nodes has a distinct distance requirement, say d(u, v). The approximation guarantees above hold provided d is replaced by max,,, d(u, v). All our algorithmic as well as hardness results hold for both undirected and directed versions of the problem. Sanjeev Khanna In the network design problem we are given a weighted undirected graph. We wish to find a subgraph which connects all the original vertices and minimizes the sum of the shortest path weights between all vertex pairs, subject to a budget constraint on the sum of its edge weights. In this note we establish NP-completeness for the network design problem, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees. This result justifies the development of enumerative optimization methods and of approximation algorithms, such as those described in a recent paper by R. Dionne and M. Florian.