Studies on Upper and Lower Approximation Bounds for Graph Optimization Problems

在这项研究中，对于许多NP-难图优化问题，我们设计了近似算法，这些算法在多项式时间内运行，并通过问题的所有可能实例上的最坏情况可能的相对误差进行数学评估。此外，我们还给出了NP-困难图优化问题的可逼近性下界。不可近似性的结果表明，除非NP=P，否则我们不能保证在多项式时间内做得更好。

In this research, for many NP-hard graph optimization problems, we designed approximation algorithms, which run in polynomial time and are mathematically evaluated by the worst case possible relative errors over all possible instances of the problems. Also, we showed the lower bounds on approximability for NP-hard graph optimization problems. The inapproximability results demonstrate that unless NP=P we cannot guarantee to do substantially better in polynomial time.