Combinatorial optimization: approximation algorithm and robust optimization

点击翻译按钮获取中文摘要

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.