Transcription of 10.1 Integer Programming and LP relaxation
{{id}} {{{paragraph}}}
Example: bachelor of science
10.1 Integer Programming and LP relaxation
CS787: Advanced AlgorithmsLecture 10: lp relaxation and RoundingIn this lecture we will design approximation algorithms using linear Programming . The key insightbehind this approach is that the closely related Integer Programming problem is NP-hard (a proofis left to the reader). We can therefore reduce any NP-complete optimization problem to an integerprogram, relax it to a linear program by removing the integrality constraints, solve the linearprogram, and then round the LP solution to a solution to the original problem. We first describethe Integer Programming problem in more Integer Programming and LP relaxationDefinition Integer program is a linear program in which all variables must be in a linear program, the constraints in an Integer program form a polytope.
f(L) 2C f(x) and C r(L) 6C r(y). Proof: For any two customers j 1 and j 2 that were picked in Step 1, S j 1 \S j 2 = ;. Consider the facility cost incurred by one execution of Steps 1 through 4. Let jbe the customer chosen in Step 1, and let ibe the facility chosen in Step 2. Since ~xis part of a feasible solution, 1 P k2S j x~ k. So, f i f i P ...
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: