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

AF:RUI:Small:参数化约束下树输出的近似问题

• 批准号: 1910565
• 负责人: Rajiv Gandhi
• 金额: $ 33.06万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910565&HistoricalAwards=false
• 关键词: AF; RUI; Small; Approximation; Problems

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.

树是计算机科学及相关领域中最重要和最基本的(数据)结构之一。这个项目试图对搜索树输出的优化问题进行全面的研究，并对关键参数进行特定的约束。经典的最小生成树(MST)问题就是所需输出为树的问题的一个例子。对于最小生成树问题，存在产生最优解的简单贪婪算法。与最小生成树问题不同，解决的大多数问题的准确解决方案被认为是难以解决的(在技术术语中，NP-Hard)。这个项目的一个目标是为这些问题设计出接近最优的解决方案。该项目的另一个重要方面是教育。培养和培养本科生和高中生是拟议项目的一个主要重点。指导和指导这些学生将丰富他们的个人，并允许他们通过他们的学术和专业努力产生更大的影响。该项目专注于其输出为树的问题，这些树对度和直径等关键参数具有约束。本课题考虑的典型问题是以图为输入，目标是寻找最大度低、成本低或直径小、成本低的树/林。当输入图是有向的或当考虑问题的更一般版本时，问题变得更加困难。这类问题的例子有k-MST、有向Steiner树和k-Steiner森林问题。这些问题是NP难的，本项目的目标是设计这些问题的近似算法，并证明其难解结果。该项目还将为本科生和高中生提供巨大的研究机会。早期接触研究将激发本科生追求学术兴趣，这将有助于加强国内计算机科学博士队伍。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

The minimum degree Group Steiner problem

最小度斯坦纳群问题

• DOI: 10.1016/j.dam.2021.12.003
• 发表时间: 2022
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Kortsarz, Guy;Nutov, Zeev
• 通讯作者: Nutov, Zeev

Approximation algorithms for connected maximum cut and related problems

连通最大割的近似算法及相关问题

• DOI: 10.1016/j.tcs.2020.01.016
• 发表时间: 2020
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Hajiaghayi, MohammadTaghi;Kortsarz, Guy;MacDavid, Robert;Purohit, Manish;Sarpatwar, Kanthi
• 通讯作者: Sarpatwar, Kanthi

Network Design under General Wireless Interference

• DOI: 10.1007/s00453-021-00866-z
• 发表时间: 2021-08
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: M. Halldórsson;G. Kortsarz;Pradipta Mitra;Tigran Tonoyan

Radio aggregation scheduling

无线聚合调度

• DOI: 10.1016/j.tcs.2020.07.032
• 发表时间: 2020
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Gandhi, Rajiv;Halldórsson, Magnús M.;Konrad, Christian;Kortsarz, Guy;Oh, Hoon
• 通讯作者: Oh, Hoon

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

近似扳手和定向斯坦纳森林：上限和下限

• DOI: 10.1145/3381451
• 发表时间: 2020
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Chlamtáč, Eden;Dinitz, Michael;Kortsarz, Guy;Laekhanukit, Bundit
• 通讯作者: Laekhanukit, Bundit