The research objective of this project is for the development of novel numerical techniques to solve computationally hard mathematical problems in combinatorial optimization that have relevant applications in network design, compressed sensing, 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, branch decompositions, for mathematical structures called matroids and symmetric submodular set functions 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 that 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 these areas.
This grant investigated the construction of novel decomposition techniques for mathematical structures called graphs, matroids, and submodular functions. These novel techniques proved fruitful to increase the scalability and efficiency of solution methods for solving computationally hard problems modeled on these mathematical structures. For example, one technique was proved to be 60 times faster than a commercial code for a particular class of problems. These particular problems have applications in biology, sensor networks, compressed sensing, machine learning, and network design. In addition, this grant fostered a number of results in research related to detecting cohesive substructures in data networks, which has applications in data mining with structured clustering. This grant also fostered research related to finding minimum objects of influence in data networks which applications in wireless networks, data mining, swarm robotic motion, and viral marketing. In all, this grant resulted in 11 journal articles and number of invited talks on the accomplished research. Finally, this grant engaged undergraduate through Research Experience for Undergraduates supplemental funding. This resulted in a number of the students choosing to go into graduate school in this area. Graduate students as well as a post-doctoral researcher were also engaged in this research. Furthermore, individuals who are traditionally underrepresented in science, technology, engineering, and mathematics fields were engaged in this research. In particular, one Indian female, one white female, one Hispanic female, and one Hispanic male were engaged in the research.
