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

在某些组合优化问题中，在寻找解的成本显著降低的情况下，得到的解可能违反某些约束。这样的问题被称为软约束问题。在硬约束问题中，可接受的解决方案不能违反任何约束。与具有软约束的相应问题相比，许多问题的硬约束版本都无法得到令人满意的解决方案。本课题的目标是研究具有硬容量约束的组合优化问题。pi将专注于网络设计的硬容量版本和设施位置问题。这些问题在网络和资源分配中都有应用，是组合优化中的核心问题之一。正如过去经常发生的那样，pi相信为解决这些问题而开发的技术将对解决其他组合问题产生更广泛的影响。培训和培养本科生和高中生是拟议项目更广泛影响的主要重点。ppi之前与本科生的合作为他们中的许多人带来了很好的就业机会。pi将继续与罗格斯-卡姆登的学生一起工作，培养他们的原始才能，帮助他们发现自己的潜力。pi还将继续与高中生合作，让他们接触到理论计算机科学，并与他们中的一些人一起进行研究。

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.