AF:RUI:Small:Approximation Problems with Tree Outputs Under Parameterized Constraints

在计算机科学和相关领域的许多领域中，树是最重要和最基本的（数据）结构之一。该项目试图对搜索树输出的优化问题进行全面研究，并对关键参数进行特定约束。经典的最小生成树（Minimum Spanning Tree， MST）问题就是一个需要输出是树的问题的例子。对于最小生成树问题，存在产生最优解的简单贪心算法。与最小生成树问题不同，大多数问题的精确解被认为是难以处理的（用技术术语来说，NP-hard）。这个项目的目标是为这些问题设计接近最优的解决方案。该项目的另一个重要方面是教育。培训和培养本科生和高中生是本项目的重点。指导和指导这些学生将丰富他们的个人，也允许他们通过他们的学术和专业努力产生更大的影响。该项目关注的问题是其输出是具有关键参数（如度和直径）约束的树。本项目考虑的典型问题以图为输入，目标是寻找最大程度低成本低或直径低成本低的树木/森林。当输入图是有向的，或者考虑到问题的更一般的版本时，问题变得更加困难。这类问题的例子有k-MST、有向斯坦纳树和k-斯坦纳森林问题。这些问题是np困难的，本项目的目标是为这些问题设计近似算法并证明硬度结果。这个项目也将为本科生和高中生提供大量的研究机会。早期接触研究将激发本科生追求学术兴趣，这将有助于加强国内计算机科学博士的培养。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Trees are among the most important and fundamental (data) structures in many areas of computer science and related fields. This project attempts to do a comprehensive study of optimization problems which search for tree outputs, with specific constraints on critical parameters. The classical Minimum Spanning Tree (MST) problem is an example of a problem in which the output required is a tree. Simple greedy algorithms that yield optimal solutions exist for the Minimum Spanning Tree problem. Unlike the minimum spanning tree problem, exact solutions for most problems that are addressed are considered intractable (in technical jargon, NP-hard). A goal in this project is to design near-optimal solutions for these problems. Another important aspect of the project is education. Training and fostering undergraduate students as well as high school students is a major emphasis of the proposed project. Guiding and mentoring these students will enrich them individually and also permit them to make a greater impact through their academic and professional endeavors. The project is focused on problems whose outputs are trees with constraints on key parameters such as degree and diameter. Typical problems considered in this project take graphs as inputs and the objective is to find trees/forests with low maximum degree and low cost or with low diameter and low cost. The problems become harder when the input graphs are directed or when more general versions of the problems are considered. Examples of such problems are the k-MST, the directed steiner tree, and the k-steiner forest problems. These problems are NP-hard and the goal of this project is to design approximation algorithms for these problems and to prove hardness results. This project will also provide tremendous research opportunities for undergraduate students as well as high school students. Early exposure to research will inspire undergraduate students to pursue academic interests and this will help strengthen the domestic PhD pipeline in computer science.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.