AF: Small: RUI: Network design and facility location problems

AF：小：RUI：网络设计和设施选址问题

• 批准号: 1218620
• 负责人: Guy Kortsarz
• 金额: $ 33.39万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218620&HistoricalAwards=false
• 关键词: AF; Small; RUI; Network; design

In some combinatorial optimization problems, the resulting solutionmay violate some constraints provided the cost of finding the solutionis significantly reduced. Such problems are called soft constraintsproblems. In hard constraints problems, an acceptable solution cannotviolate any of the constraints. Hard constraints versions of manyproblems have resisted satisfactory solutions as compared to thecorresponding problems with soft constraints. The goal ofthis project is to study combinatorial optimization problems with hardcapacity constraints. The PIs will be focusing on hard capacity versions of network designand facility location problems. These problems have applications innetworking and resource allocation and are among the central problemsin combinatorial optimization. As it has happened often in the past,the PIs believe that techniques developed for solving these problemswill have broader impact in solving other combinatorial problems. Training and fostering undergraduate as well as high school studentsis a major emphasis of the broader impact of the proposed project.The PIs' prior work with undergraduates have led to very good careeropportunities for many of them. The PIs will continue working withstudents at Rutgers-Camden, fostering their raw talent and helpingthem discover their own potential. The PIs will also continue workingwith high school students, giving them exposure to theoreticalcomputer science and working on research with some of them.

在某些组合优化问题中，由此产生的解决方案违反了一些限制，提供了查找解决方案的成本大大减少。这样的问题称为软约束串联。在严格的约束问题中，可接受的解决方案不能侵犯任何约束。与具有软限制的问题相比，多个问题的硬约束版本已抵制令人满意的解决方案。这个项目的目标是研究与硬度约束的组合优化问题。 PI将重点关注网络设计和设施位置问题的硬容量版本。这些问题具有应用程序和资源分配，并且是组合优化的中心问题之一。正如过去经常发生的那样，PIS认为，为解决这些问题设备而开发的技术在解决其他组合问题方面具有更大的影响。培训和培养本科生以及高中生对拟议项目的更广泛影响的主要重点。 PI将继续与Rutgers-Camden的学生一起工作，培养其原始人才并帮助发现自己的潜力。 PI还将继续与高中生一起工作，使他们接触理论计算机科学，并与其中一些研究进行研究。