PDF4PRO ⚡AMP

Modern search engine that looking for books and documents around the web

Example: stock market

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.

region of the LP is larger than the feasible region of the IP, the optimal value of the former is no worse than the optimal value of the latter. This implies that the optimal value to the LP is a lower bound on OPT, the optimal value for the problem we started out with. While the rounded solution

Loading..

Tags:

  Regions, Relaxation, Lp relaxation

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Spam in document Broken preview Other abuse

Transcription of 10.1 Integer Programming and LP relaxation

Related search queries