Algorithmic and game-theoretic analysis and implementation of network design

点击翻译按钮获取中文摘要

Network problems are among the most basic optimization problems. Whether the goods transfered through them are data or commodities they must be designed so as to optimize metrics such as time, costs, or revenue. It has been long known that although these networks may be very different, their modelling can capture their underlying common characteristics. A very recent manifestation of this trend (alongside the older examples of network flow, routing, fault tolerance etc.) is the introduction of selfish behaviour in the study of large data and communication networks such as the Internet; while this is a new paradigm for most computer scientists, it has been studied for more than 50 years by economists and the transportation community. The design of network protocols based on auction mechanism design is another such example. The purpose of this research is to explore the application of these new paradigms in network design from an algorithmic point of view, alongside the study of more `traditional' aspects such as the development, analysis and implementation of better approximation algorithms for network flow and routing problems. In a world that is more inter-connected than ever, the expectation of this research proposal is to have a significant impact on the more efficient distribution of information, goods, services etc.