Optimal Knapsack Algorithms
Explore approximate algorithms such as greedy and dynamic programming for the knapsack problem. Understand how these algorithms aim to find solutions that are close to optimal while managing computational complexity efficiently.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Approximate Greedy For some problems, the obvious greedy algorithm does not give always give the most optimal solution, but may guarantee that it gives one that is within say a factor of 2 of optimal. Max Cut: A random cut expects to have half the edges cross it.
Approximate Knapsack Get as much value as you can into the knapsack
Approximate Knapsack Ingredients: Instances: The volume V of the knapsack. The volume and price of n objects <<v1,p1>,<v2,p2>, ,<vn,pn>>. Solutions: A set of objects that fit in the knapsack. i.e. i S vi V Cost of Solution: The total value of objects in set. i.e. i S pi Goal: Get as much value as you can into the knapsack.
Approximate Knapsack Dynamic Programming Running time = ( V n ) = ( 2#bits in V n ) Poly time if size of knapsack is small Exponential time if size is an arbitrary integer.
Approximate Knapsack Dynamic Programming Running time = ( V n ) = ( 2#bits in V n ) NP-Complete Approximate Algorithm In poly-time (n3/ ), solution can be found that is perfect in i S vi V (1+ ) as good as optimal wrt i S pi Eg, = .001, Time is 1000n3
Approximate Knapsack Subinstance: V [0..V], i [0..n], knapsack(V ,i) = maximize i S pi subject to S {1..i} and i S vi V Recurrence Relation knapsack(V ,i) = max( knapsack(V ,i-1), knapsack(V -vi,i-1)+pi ) No Yes
Approximate Knapsack V [0..V], i [0..n], knapsack(V ,i) 0 1 2 V -vi V V OptSol price 0 1 2 same + pi No i-1 i same Yes Take best of best. Our price? n
Approximate Knapsack V [0..V], i [0..n], knapsack(V ,i) 0 1 2 V V OptSol price 0 1 2 i-1 i Time = O(nV) n
Approximate Knapsack Ingredients: (strange version) Instances: The price P wanted from the knapsack. The volume and price of n objects <<v1,p1>,<v2,p2>, ,<vn,pn>>. Solutions: A set of objects with total value P. i.e. i S pi P Cost of Solution: The total volume of objects in set. i.e. i S vi Goal: Minimize the volume needed to obtain this value P.
Approximate Knapsack Subinstance: P [0..P], i [0..n], knapsack (P ,i) = minimize i S vi subject to S {1..i} and i S pi P Recurrence Relation knapsack (P ,i) = min( knapsack (P ,i-1), knapsack (P -pi,i-1)+vi ) No Yes
Approximate Knapsack V [0..V], i [0..n], knapsack (P ,i) 0 1 2 P -pi P P OptSol volume 0 1 2 same + vi No i-1 i same Yes Take best of best. Our volume? n
Approximate Knapsack Original problem knapsack(V,n) 0 1 2 P P OptSol volume 0 1 2 i Find largest price not using more than V volume Time = O(nP) P = i pi n
Approximate Knapsack Dynamic Programming Running time = ( V n ) = ( 2#bits in V n ) Poly time if size of knapsack is small Exponential time if size is an arbitrary integer. Strange Dynamic Programming Running time = ( P n ) = ( 2#bits in P n ) Poly time if prices are small Exponential time if prices are arbitrary integers.
Approximate Knapsack Approximation Algorithm: Given V, <<v1,p1>,<v2,p2>, ,<vn,pn>>, & Lose precision in prices. eg pi = 1011011010112 p i = pi with low k bits removed = 101101102 p i = pi with low k bits zeroed = 1011011000002 Solve knapsack using the strange algorithm. 10110110 k=4 (k chosen later) = pi / 2k or pi - 2k
Approximate Knapsack Original problem knapsack(V,n) 0 1 2 P P OptSol volume 0 1 2 i Time = O(n P) = O(n P/2k) n
Approximate Knapsack Approximation Algorithm: Let Salg be the set of items selected by our alg. Let Sopt be the set of items in the optimal sol. pi i Salg pi i Sopt Need Palg Popt (1- ) Let Palg = be the price returned by our alg. Let Popt = be the price returned by our alg.
Approximate Knapsack = pi i Salg p i i Salg p i i Sopt (pi -2k) i Sopt = Popt n 2k Palg because rounded down because Salg is an optimal solution for the <vi,p i> problem because rounded by at most 2k.
Approximate Knapsack Palg Popt n2k Popt Popt n Time = O(n P/2k) = O( n2 P ) (need) n2k Popt = 1 - = 1 - Popt 2k = Popt P = i pi Time = O( n3) Popt maxi pi P n done
Approximate Clique Clique: Given <G,k>, does G contains a k-clique? Brute Force: Try out all n choose k possible subsets. If k = (n) then 2 (n) subsets to check If k=3 then only O(n3) NP-Complete: ie, if there is a poly time algorithm for it, then there is one for many important problems.
Approximate Clique Clique: Given <G,k>, does G contains a k-clique? Given a graph G, how well can you approximate the size of the largest clique? Not at all. It is NP-complete to know if the largest clique is of size n or n1-
