c****m
发帖数: 91 | 1
我不是高手,但是做N-dimensional assignment一段时间了,下面
写的是一些已知的结果:
你的问题是一个2-D assignment问题,可以relax integer constraints,
用LP求解,最好是用primal-dual interior point method.
如果是sparse问题,modified auction可以很快得到结果,如果是dense
问题,偶觉得JVC比较合适.如果能separate问题to subproblems,也许可以
分别用auction和JVC解相应的子问题.如果你知道其中一些约束,问题是能
不能转化为linear cost flow问题,如果可以,则偶推荐用auction求解.不
能的话对提高运算速度从worst case角度看无帮助.
对3-D以上assignment问题,通常搜索最优解是NP hard,此时不能relax integer
constraints,但是可以解dual problem using successive Lagrangian relaxation.
偶最近提出用LP解primal p | c****m
发帖数: 91 | 2
再说一遍,偶不是高手.谁证明的Hungarian只有O(N^3),和矩阵求逆一个量级的?
看看Dimitri P. Bertsekas的书,象auction很难简单用O(N^k)来分析的,和许多
因素有关.JVC是偶知道的目前最popular的算法,其改进版本很多.如果你知道
一些assignment bipartites,等于加了新的constraints,如果能化简为linear
network flow,潜在变量数就小于N,否则偶还是不知道算法复杂性如何降低.
有时间看看
http://archives.math.utk.edu/topics/discreteMath.html
也许会有帮助.
偶前面说的关于assignment solutions也请参见
R. L. Popp, T. Kirubarajan, and K. R. Pattipati, "Survey of Assignment
Techniques for Multitarget Tracking", Chapter 2 in Multitarget/Multisensor
Tracking: Applica |
|
