Greedy Algorithm
in [Theory]
|
From: Googmeister on 11 Apr 2006 12:28 Mitch wrote: > Googmeister wrote: > > > Here's a reference to a proof. > > > > TI : Optimality of a Heuristic Solution for a Class of Knapsack > > Problems > > AU : Hu, T. C.; Lenard, M. L. > > VO : 24 > > NO : 1 > > DA : Jan. - Feb., 1976 > > PP : 193-196 > > AB : This paper presents a simpler proof for a result of Magazine, > > Nemhauser, and Trotter, which states recursive necessary and sufficient > > conditions for the optimality of a heuristic solution for a class of > > knapsack problems. > > ..where the journal is presumably "Operations Research". Yes, sorry for the omission.
From: Googmeister on 11 Apr 2006 12:31 Woeginger Gerhard wrote: > Googmeister <googmeister(a)gmail.com> wrote: > # > # jason_box wrote: > #> Hello, I was wondering if there is a general proof on proving the > #> optimal solution for making change with the standard Greedy Alogorithm > #> example for change making. I wanted to prove that for any given > #> denomination say C = {8, 4, 2 , 1} for any positive integer n that the > #> greedy algorithm will make change for n using the smallest amount of > #> coins. > # > # Magazine, Nemhauser, and Trotter gave necessary and sufficient > # conditions for when the greedy coin changing algorithm is optimal. > # The proof is algorithmic - given a set of denominations, > # you can efficiently determine whether the greedy algorithm is > # optimal or not. > > Yes, Magazine, Nemhauser, and Trotter gave conditions for when > the greedy coin changing algorithm is optimal. > > No, their proof does not help to "efficiently" determine (in > polynomial time) whether the greedy algorithm is optimal > for a given denomination system. > > The first efficient algorithm for this problem is due to David > Pearson, who derived it in his PhD thesis (Cornell, 1994). > This result was published ten years later as > > David Pearson > A polynomial-time algorithm for the change-making problem > Operations Research Letters 33, 2005, pages 231-234 > > The proof is beautiful. Thanks! I stand corrected. I found an online version (perhaps a bit old) here. http://citeseer.ist.psu.edu/pearson94polynomialtime.html
From: jason_box on 11 Apr 2006 14:55
I think I am only to use a general proof on if the denomination C = {8,4,2,1} would be optimal with the greedy algorithm and not having to compute the complexity. I think also having the coins be a multiple of each other helps but I'm unsure on where to take the proof from there. If anyone could guide me in showing that with these denominations, the greedy approach will be the most optimal. Thank you once again. |