@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/v8w2R9Lq69MJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
