Branch Decomposition Techniques for Submodular Optimization

该项目的研究目标是开发新的数值技术来解决组合优化中的计算困难的数学问题，这些问题在网络设计，压缩传感，传感器网络和生物学中具有相关应用。 所开发的技术将用于提高在这些研究领域解决的问题的可扩展性。 具体来说，该研究将开发创新技术，以产生一个特定的，但重要的分解结构，分支分解，称为拟阵和对称子模集函数，用于数学建模这些问题的数学结构。 为此，所开发的技术将与文献中的其他精确算法进行比较，以验证和评估该技术的计算效率。如果成功，结果将提高解决感兴趣问题的可扩展性和效率。 这些问题的应用是在领域看到增加的服务需求。 此外，其结果可以用来解决其他相关的计算困难的问题，在组合优化，具有广泛的应用，除了上述应用。 因此，这些结果将推进组合优化中的知识库，并为解决这些领域中的大规模问题提供新的有效技术。

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.