III: Small: A primal-dual framework for data-mining applications

移动设备和社交网络的激增使人们能够收集与用户活动有关的广泛信息。收集的信息可以表示为捕获用户之间的互连的网络，网络中的节点被来自用户活动的额外信息丰富。这类网络的例子包括活动公路网和标志性公路网，其中节点是交叉口，边缘是路段。活动网络中的每个节点都与某种类型的活动相关联，例如从节点附近上传的带有地理标记的推文或照片。在地标网络中，节点与博物馆、餐馆和地标等兴趣点相关联。在这种网络的分析中出现的一个基本任务是找到一组在网络中靠近并且也与高活跃度相关联的连接节点。例如，这样的分析可以用来确定社区的利益以及关于人口动态的有趣事实。类似的问题也出现在社交和协作网络、专业知识管理系统和团队组建方面。网络通常是大规模的，因此解决这些优化任务需要非常高效的算法，并且允许对数据进行更丰富和更有信息量的分析。该项目将上述应用中出现的优化问题建模为获奖网络设计问题：给定一个图，其连接成本与边相关联，并且与节点相关联，目标是找到具有较小连接成本和较高奖金的连通子图。为了进行更丰富的分析，该项目考虑了更复杂的集合奖励函数，其中包括节点之间的交互以及在目标中结合连接成本和奖励的不同方式。该方法是利用模板原始-对偶框架为每一类问题设计算法，该框架受获奖Steiner树问题的经典算法的启发。设置奖品的不同实例化需要重新设计该模板算法的特定组件，从而导致新的算法研究方向。一个重要的目标是利用应用程序中出现的奖励函数的结构，以获得非常高效和可扩展的算法，以及实现可证明的近似保证。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.