Combinatorial optimization: approximation algorithm and robust optimization

该研究计划的目标是开发组合优化问题的通用算法理论，这些理论预计将对供应链管理、生产/运营管理、网络流、位置和路由、调度、电信、运输、健康、生物信息学等应用产生重大影响。*具有可证明性能的近似算法是解决大规模NP-hard组合优化问题的一个有价值的选择。鲁棒优化是一种竞争模式，用于解决只有不完整的潜在问题信息时的优化问题，使得经典的随机优化在必须知道潜在概率分布的全部知识时变得不合适。这两个研究领域仍在快速发展，留下了许多深刻的问题没有得到解答。更重要的是，在大数据时代，采用这些方法解决现实问题仍处于起步阶段。*我们希望研究一些与近似算法和鲁棒优化相关的具体问题。这些具体问题是经过精心挑选的，因此它们具有代表性，基础性，基础性，并且在推进相应主观领域的知识方面具有很大的潜力，并在很大程度上产生新的方法。此外，所研究的问题不仅具有理论意义，而且具有重要的现实意义。我们选择的问题涵盖了设施选址理论、集合和搜索、网络流、供应链管理、财务优化和调度等主观领域。拟议的研究建立在我们以前的工作和我们过去在解决上述一些问题方面的成功之上，这表明我们有必要的数学基础和适当的工具来解决这些问题。*这项调查的结果不仅会导致有效的算法和加强对所考虑的特定问题的理解，而且还将为创新潜在的新机制奠定基础，这些新机制对加拿大和国际商业和经济的管理具有重大的实际意义和重要性。

The objective of the research program is to develop general algorithmic theories in combinatorial optimization problems that are expected to have a significant impact on such applications as supply chain management, production/operations management, network flow, location and routing, scheduling, telecommunication, transportation, health, bioinformatics, and others. *Approximation algorithm with provable performance is a valuable option for solving large-scale NP-hard combinatorial optimization problems. Robust optimization is a competitive paradigm to solve optimization problems when only incomplete information on the underlying problems is available, rendering the classical stochastic optimization inappropriate where the full knowledge of the underlying probability distribution must be known. These two research areas are still developing at a rapid pace, and leave many profound questions unanswered. More important, the adoption of these methods into real-world problems is still in its infancy in the big data era. *We wish to study some specific problems related to approximation algorithm and robust optimization. These specific problems are carefully chosen such that that they are representative, basic, fundamental, and possess great potential in advancing the knowledge of the corresponding subjective areas in particular and spawning new methodologies at large. Moreover, the problems to be investigated are not only of theoretical importance, but also great practical significance. We have selected problems that span the subjective areas of facility location theory, rendezvous and search, network flow, supply chain management, finance optimization, and scheduling. The proposed research builds upon our previous work and our past success in attacking some of the aforementioned problems is an indicator that we have the necessary mathematical groundings and proper tools to work on them. *The results of this investigation will not only lead to efficient algorithms and enhanced understanding for the particular problems under consideration, but will also build foundations to innovate potential new mechanisms that are of great practical significance and importance to the management of Canadian and international business and economics.