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.
|Effective start/end date||9/1/12 → 8/31/15|
- National Science Foundation (National Science Foundation (NSF))