JVC is a multi-part algorithm which consists of a shortest augmenting path algorithm (JV) followed by a modified auction algorithm (C). It is best implemented as a sparse matrix. JVC is definitely an example of efficiency requiring a significant increase in complexity. The code implementing JVC is several times larger than Munkres or a standard auction algorithm.
Here are some references: The "JV" part is here R. Jonker, A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assign- ment problems.Computing, Vol. 38, 1987, pp.325- 340. A thorough evaluation of JVC is here: D.B. Malkoff. Evaluation of the Jonker-Volgenant- Castanon (JVC) Assignment Algorithm for Track Association Proceedings of the SPIE Aerosense'97 Conf. on Signal Proc., Sensor Fusion, and Target Recognition, Vol. 3068, 1997, pp. 228-239. A description of JVC is here: O.E. Drummond, D.A. Castanon, M.S. Bellovin. Comparison of 2-D Assignment for Sparse, Rect- angular, Floating Point, Cost Matrix. Journal of the SDI Panels on Tracking, Institute for Defense Analyses, Issue No.4, 1990, pp.4-81 to 4-97. On Mar 3, 10:15 pm, Dave <dave_and_da...@juno.com> wrote: > @Don: I've looked for a description of Jonker-Volgenant-Castanon, but > haven't found one. Can you provide a reference? > > Dave > > > > On Tuesday, February 28, 2012 11:53:22 AM UTC-6, Don wrote: > > Dave's answer, the Hungarian Algorithm, is correct because it does > > meet the requirements of the problem. > > There is another algorithm called Jonker-Volgenant-Castanon (JVC) > > which can be proven to be faster both on average and in worst case, > > than the Hungarian Algorithm. Both solutions are sure to find the best > > solution, which is not true of any ad hoc or greedy algorithm. For > > years, the Munkres algorithm was the best known solution, but JVC is > > significantly faster than Munkres. > > > Don > > > On Feb 28, 11:39 am, Don <dondod...@gmail.com> wrote: > > > Yes, the tags constrain him to buy exactly one candy from each row and > > > each column. > > > There is a slightly better algorithm than Hungarian. > > > Don > > > > On Feb 28, 11:33 am, Dave <dave_and_da...@juno.com> wrote: > > > > > @Don: Based on your example, there seems to be an unstated requirement > > > > that Bob can and must buy exactly one candy from each row and each > > > > column. > > > > > This is an assignment problem (see en.wikipedia.org/wiki/ > > > > Assignment_problem), and can be solved in O(N^3) by the Hungarian > > > > Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm). > > > > > Dave > > > > > On Feb 28, 9:27 am, Don <dondod...@gmail.com> wrote: > > > > > > Little Bob likes candy, and he wants to buy all the candy he can get > > > > > for the smallest price. At the store there is a big table with candy > > > > > arranged in an NxN grid. Each candy has a price, Pij where i is the > > > > > row and j is the column in which the candy is located. The store > > owner > > > > > gives Bob N tags numbered 1..N. Bob can place one tag at the top of > > > > > each column indicating the piece of candy he will buy from that > > > > > column. > > > > > > Bob is smart enough to realize that he should not always buy the > > least > > > > > expensive candy. For example, consider this price grid: > > > > > > 1 20 > > > > > 5 50 > > > > > > In this case, buying the candy priced 1 would force him to buy the > > > > > candy priced 50, for a total cost of 51. He is better off buying the > > > > > second candy in the first column, allowing him to buy the first > > candy > > > > > in the second column for a total price of 25. > > > > > > For a 2x2 case, considering all the possibilities is easy enough. > > > > > There are only two choices. But as N increases, the number of ways > > to > > > > > select N candies increases as N!, and Bob doesn't have time for an > > > > > algorithm which requires more than polynomial time to execute. > > > > > > What algorithm should Bob use to buy N pieces of candy for the > > > > > smallest cost?- Hide quoted text - > > > > > - Show quoted text -- Hide quoted text - > > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
