网络优化的逆问题及网络改进问题的算法研究

近二十年来，网络优化的逆问题与网络改进问题得到了国内外学者的广泛关注，成为组合最优化及图论领域的一个重要课题，它同时也具有较大的实际意义与应用价值。对于许多网络优化问题，如果它们是多项式时间可解的，则其逆问题或改进问题也有多项式时间算法。然而，还有一些优化问题的逆问题或改进问题是NP-难问题。研究NP-难问题的近似算法或其特殊情形的多项式时间算法是当前的一个重要的热点问题。国内外许多学者在这些方面做了大量的研究工作。本项目将着重从以下几方面对网络优化的逆问题与改进问题进行研究：1、对一些其自身为强多项式时间可解、但目前尚不知其逆问题或改进问题是否有强多项式时间算法的问题进行深入地研究；2、对一些NP-难的逆问题或改进问题，得到其具有较好性能比的近似算法或其特殊情形的多项式时间算法；3、探讨具有普遍意义的算法设计技巧，在多项式时间算法和近似算法的设计上得到具有一定创新性的研究成果。