最小曼哈顿网络问题的困难
发布网友
发布时间：2022-04-28 20:59
共1个回答
热心网友
时间：2022-06-23 04:32
最小曼哈顿网络问题的是否NP-难问题仍属未知，其不可近似性亦不清楚。因此，研究这一问题所属的复杂性类将具有极大的理论意义和实际价值。
郭泽宇提出解决最小曼哈顿网络的算法复杂性NP难问题是不太现实的，但改善现有解决方案的效率或提高近似度是可行的研究方向，郭泽宇的结果是2-近似O(n2)时间复杂度。能否将效率提高到O(nlogn)，与3-近似方法相同？或提出1.5-近似的新方法是亟待解决的新问题。
