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

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.