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

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

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.