Studies on Upper and Lower Approximation Bounds for Graph Optimization Problems

在本研究中，对于许多NP-hard图优化问题，我们设计了近似算法，该算法在多项式时间内运行，并在所有可能的问题实例中通过最坏情况下可能的相对误差进行数学评估。同时，我们也给出了NP-hard图优化问题的近似下界。不可逼近性结果表明，除非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.