|
|
|
|
|
|
|
Communication networks and more in general distributed systems are undergoing rapid advancements. The last few years have experienced a steep growth in research on different related aspects. However, although the great promise for our future communication capabilities, several challenges need still to be addressed. We focus on the analysis of the performance and complexity of optical networks (representing the main contribution) and wireless networks. More specifically, we consider classical combinatorial optimization problems arising in communication networks from two different perspectives. In the first part we consider the design of classical centralized polynomial time (approximation or exact) algorithms. Such an investigation is conducted under a traditional computational complexity setting in which time constraints must be taking into account for tractability and efficiency matters. The above perspective implicitly or explicitly assumes that the resources of the system are directly accessible and controllable by a centralized authority, but this assumption in highly distributed systems might be too strong or unrealistic. Therefore, in the second part we consider communication problems arising in networks with autonomous or non-cooperative users. In such a scenario users pursue an own often selfish strategy and the system evolves as a consequence of the interactions among them. The interesting arising scenario is thus characterized by the conflicting needs of the users aiming to maximize their personal profit and of the system wishing to compute a socially efficient solution. Algorithmic Game theory is considered the most powerful tool dealing with such non-cooperative environments in which the lack of coordination yields inefficiencies. In such a scenario we consider the pure Nash equilibrium as the outcome of the game and in turn as the concept capturing the notion of stable solution of the system. Under the above perspectives, we present different progresses on the understanding of a variety of problems in communication networks. Our results include: polynomial time algorithms, NP-complete results, approximation algorithms and inapproximability results; analysis of performances, convergence and existence of Nash equilibria in selfish scenarios.
|
|
|
|
|
|
|
|