Innovative Techniques for Constructing Branch Decompositions

William Marsh Rice University, Houston TX

Investigators

Abstract

This grant provides funding for the development of novel numerical techniques to solve computationally hard mathematical problems in combinatorial optimization that have relevant applications in network design, sensor networks, and biology. The developed techniques will be used to increase the scalability of problems solved in these research areas. Specifically, the research will develop innovative techniques to produce a specific but vital decomposition structure, called a branch decomposition, for mathematical structures called graphs that are used to mathematically model these problems. To this end, the developed techniques will be compared with other exact algorithms in the literature to validate and assess the computational efficacy of the techniques. If successful, the results will increase the scalability and efficiency of solving the problems of interest. Applications of these problems are in fields seeing increased demand for services. In addition, the results can be used to solve other related computationally hard problems in combinatorial optimization which have a wide range of applications apart from the aforementioned applications. Thus, the results will advance the knowledge base in combinatorial optimization and offer new effective techniques for solving large-scale problems in the areas.