NP优化问题的难近似性,随机算法和在线算法

In the most situations,many optimization problems in development and application of computer systems are NP-hard.We have studied the approximation algorithms of NP optimization problems from two aspects.First, some theoretically quick and practical algorithms(e.g. randomization algorithms)are designed. Second,the lower bound of approximation of NP-hard optimization problems is studied and so is how much they can be approximized. On the other hand,we have studied such problems as probabilistically checkable proof systems(PCP),NP hard problems with application to cryptography,zero-knowledge proof systems, and we have made great contributions in these fields. Finally,we also keep an eye on the new theory and technology in algorithm design, such as randomization algorithms ,derandomization algorithms, and online algorithms, some results are also made in these fields.

NP 最优问题安其难近似性,依照一定的规约可分的不同的类.我们将安SL归纳对其做出一步阜?另外,对某些重要问题,如整数规划,页面调度,可满足性问题研究性能较好的随机算法或在线算法.