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将专注于网络设计和设施位置问题的硬容量版本。这些问题在网络和资源分配中有应用，并且是组合优化中的中心问题。正如过去经常发生的那样，PI相信为解决这些问题而开发的技术将在解决其他组合问题方面产生更广泛的影响。培训和培养本科生以及高中生是拟议项目更广泛影响的一个主要重点。PI先前与本科生的工作为他们中的许多人带来了非常好的职业机会。PI将继续与罗格斯-卡姆登大学的学生合作，培养他们的天赋，帮助他们发现自己的潜力。 PI还将继续与高中生合作，让他们接触理论计算机科学，并与其中一些人一起进行研究。