有人知道网络单纯形法时间复杂度吗?
网络单纯形法是求解线性规划的算法,主要用于求解费用流。随机图中效率大概是 O(nm)O(nm)O(nm),是实际使用中效率最高的费用流算法,将费用设成零甚至能过HLPP 板子题。 但网络单纯形法时间复杂度上限据说很高,但我查到的复杂度上限只说是“指数型复杂度”,都没给出具体的复杂度。
网络单纯形法是求解线性规划的算法,主要用于求解费用流。随机图中效率大概是 O(nm)O(nm)O(nm),是实际使用中效率最高的费用流算法,将费用设成零甚至能过HLPP 板子题。
但网络单纯形法时间复杂度上限据说很高,但我查到的复杂度上限只说是“指数型复杂度”,都没给出具体的复杂度。