The proliferation of mobile devices and social networks has enabled the collection of a wide-range of information related to users' activities. The collected information can be represented as a network capturing the inter-connections between users and the nodes in the network are enriched with extra information resulting from users' activities. Examples of such networks include activity and landmark road networks where the nodes are intersections and the edges are road segments. Every node in an activity network is associated with some type of activity such as geotagged tweets or photos uploaded from the node's vicinity. In landmark networks, nodes are associated with points of interests such as museums, restaurants, and landmarks. A fundamental task arising in the analysis of such networks is to find a set of connected nodes that are close-by in the network and are also associated with high levels of activity. For example, such an analysis can be used to identify the interests of neighborhoods as well as interesting facts about population dynamics. Analogous problems arise in social and collaboration networks, expertise management systems, and team formation. The networks are often massive and thus solving these optimization tasks requires algorithms that are very efficient and allow for a richer and more informative analysis of the data.
The project models the optimization problems arising in the aforementioned applications as prize-collecting network design problems: given a graph with connection costs associated with the edges and prizes associated with the nodes, the goal is to find a connected subgraph that has small connection cost as well as high prize. To allow for a richer analysis, the project considers more complex set prize functions that incorporate interactions between nodes and different ways of combining the connection cost and the prize in the objective. The approach is to design algorithms for each class of problems using a template primal-dual framework motivated by the classical algorithm for the prize-collecting Steiner tree problem. Different instantiations of the set prizes require the re-design of specific components of this template algorithm and thus lead to new algorithmic research directions. An important goal is to exploit the structure of the prize functions arising in applications in order to obtain algorithms are very efficient and scalable, in addition to achieving provable approximation guarantees.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
