Approximation algorithms for hard optimization problems in multi-omics research and operations research

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

The proposed research program focuses on designing efficient algorithms with provable performance for computational optimization problems inspired by real world applications, in particular from multi-omics research and operations research. When facing a challenging real world application, the typical process is first to formulate the problem mathematically, to pursue the optimization of a specified objective function. The optimization problem is then studied to understand its level of difficulty and to design algorithms supported by a rigorous analysis of its efficiency, performance and correctness. But most of our target problems arising from challenging applications cannot be solved optimally in polynomial time, unless P = NP. We follow the line of main stream research to study the in-/approximability of the problems and to design approximation algorithms for the problems. Additionally, we will study the fixed parameter tractability of the problems and seek to pioneer the fixed parameter approximability. Approximation algorithms run in polynomial time and produce solutions that are guaranteed to be within a certain factor of the optimal solution. The study of the design and analysis of approximation algorithms has multi-faceted impact: 1) due to the intractability of the target optimization problem, an approximation algorithm at least gives a way to find a near-optimal solution with provable guarantee; 2) although the worst-case performance guarantee may appear disappointing, an approximation algorithm can frequently perform really well on real world instances; and 3) most importantly, the developed algorithmic tools and design-and-analysis techniques can be generally useful, even if the approximation algorithm by itself may not be very practical. While approximation algorithms are positive results for approaching an NP-hard problem, it is also important to study the limit of such approximation, known as the hardness of approximation or inapproximability. By proving lower bounds on approximability of the problems, we achieve deeper insights on the spectrum of the NP-hard optimization problems. Such insights can in turn be used to develop new and better approximation algorithms. The tractability and the approximability of the problem could change along with the (often multiple) parameters and/or output. Fixed parameter tractability has been extensively investigated, but results on how the approximability of the problems changes along with the parameters in the input or output are limited. The study on approximation algorithms with both running time and performance ratio depending on a parameter k has the same multi-faceted aspects as stated in the above, and additionally provides insights on the parameter k and subsequently another deeper understanding of the internal spectrum of the target optimization problem.