In some combinatorial optimization problems, the resulting solution may violate some constraints provided the cost of finding the solution is significantly reduced. Such problems are called soft constraints problems. In hard constraints problems, an acceptable solution cannot violate any of the constraints. Hard constraints versions of many problems have resisted satisfactory solutions as compared to the corresponding problems with soft constraints. The goal of this project is to study combinatorial optimization problems with hard capacity constraints.
The PIs will be focusing on hard capacity versions of network design and facility location problems. These problems have applications in networking and resource allocation and are among the central problems in combinatorial optimization. As it has happened often in the past, the PIs believe that techniques developed for solving these problems will have broader impact in solving other combinatorial problems.
Training and fostering undergraduate as well as high school students is a major emphasis of the broader impact of the proposed project. The PIs' prior work with undergraduates have led to very good career opportunities for many of them. The PIs will continue working with students at Rutgers-Camden, fostering their raw talent and helping them discover their own potential. The PIs will also continue working with high school students, giving them exposure to theoretical computer science and working on research with some of them.
