【^_^】复旦学生历时两年多破解11年“最小曼哈顿网络问题”--2009-06-24

conwood

“破解”这个词用的不合适。

下面这个pdf应该是郭的最新进展。
http://www.madalgo.au.dk/socg200 ... bstracts/4_Chin.pdf

从摘要上看，他们证明了“最小曼哈顿网络问题”是强NP-完全问题。从欣然爹的帖子来看，似乎在这之前，郭还给出了一个效率更高的近似算法。当然，最有意义的还是NP-完全性的证明。

摘要上说是把3-SAT问题规约到了这个问题，目前还没找到论文的全文，不过可以想象的是，那一定是个非常美妙的规约。