AF: Small: Approximation Algorithms and Topological Graph Theory

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

Large and complex interconnected systems have become ubiquitous in the modern world, from science and engineering, to finance and commerce. In many scenarios, the structure of such systems is modeled by networks of interacting entities. This modeling paradigm can be used when studying a plethora of natural objects and phenomena, such as the web, networks of all kinds - social, transportation, communication, phylogenetic - financial transactions, and so on. The analysis of large and complex networks is therefore a task of increasing importance to society. However, reaping the potential benefits from the analysis of these objects poses great new challenges for computational sciences. Even though the statistical analysis of interconnected structures has been the subject of intense study for several decades, many of the current methods are inadequate for modern data sets. At the high level, there are two main reasons for this inadequacy. First, a key task in the analysis of networks is the discovery of useful structure. That is, finding a network representation that reveals useful information. For example, when studying a social network, it can be useful to know whether specific patterns occur in the sets of friendships between users. Unfortunately, the increasing ability to record large amounts of data has given rise to networks of unprecedented size. As a consequence, methods that were originally designed for discovering structures in smaller networks, require prohibitively large amounts of computational resources to be useful in these scenarios. Second, having discovered some useful structure in a network, it is often desirable to exploit it through further computations. For example, given a transportation network with a certain topology, one might want to design shipping methods that take advantage of this structure. Performing such computations has become exceedingly intractable in real-world data sets due to the fact that contemporary networks exhibit structure of increasingly high complexity. Many current methods for exploiting network structure are only applicable to cases of moderate complexity, and are therefore inapplicable.This project investigates new methods for discovering and exploiting structure in networks of large size, and large complexity. The research effort will focus on designing new algorithms for these two classes of problems using ideas from the so-called theory of approximation algorithms. These are algorithms that aim to allow a small amount of error, in exchange for significantly better computational performance. Existing work on this type of algorithm suggests that this is a promising direction for overcoming the barriers of network size and complexity outlined above. Broader impacts of the project include graduate training and the development of a new graduate course.