|
==Solution quality of relaxed and original programs==
The LP-linear programming relaxation of an integer program may be solved using any standard linear programming technique. If the optimal solution to the linear program happens to have all variables either 0 or 1, it will also be an optimal solution to the original integer program. However, this is generally not true, except for some special cases (e.g.,
problems with [[totally unimodular]] matrix specifications.)
==Approximation and integrality gap==
LPLinear programming relaxation is a standard technique for designing [[approximation algorithm]]s for hard optimization problems. In this application, an important concept is the [[integrality gap]], the maximum ratio between the solution quality of the integer program and of its relaxation. Typically, this gap translates into the [[approximation ratio]] of an approximation algorithm.
For the set cover problem, Lovász proved that the integrality gap for an instance with ''n'' elements is ''H<sub>n</sub>'', the ''n''th [[harmonic number]]. ThisOne matchescan turn the linear programming relaxation for this problem into an approximation ratiovia the technique of ''randomized rounding'' {{harv|Raghavan|Tompson|1987}}. Given a fractional cover, in which each set ''S<sub>i</sub>'' has weight ''w<sub>i</sub>'', choose randomly the value of each 0-1 indicator variable ''x<sub>i</sub>'' to be 1 with probability ''w<sub>i</sub>'' ×(ln ''n'' +1), and 0 otherwise. Then any element ''e<sub>j</sub>'' has probability less than 1/(''e'' ×''n'') of remaining uncovered, so with constant probability all elements are covered. The cover generated by this technique has total size, with high probability, (1+o(1))(ln ''n'')''W'', where ''W'' is the total weight of the fractional solution. Thus, this technique leads to a [[greedyRandomized algorithm|randomized]] forapproximation approximatingalgorithm that finds a set cover within a logarithmic factor of the optimaloptimum. As {{harvtxt|Young|1995}} showed, both the random part of this algorithm and the need to construct an explicit solution to the linear programming relaxation may be eliminated using the method of conditional probabilities, leading to a deterministic [[greedy algorithm]] for set cover, byknown already to Lovász, that repeatedly selectingselects the set that covers the largest possible number of remaining uncovered elements. This greedy algorithm approximates the set cover to within the same ''H<sub>n</sub>'' factor that Lovász proved as the integrality gap for set cover. There are strong complexity-theoretic reasons for believing that no polynomial time approximation algorithm can achieve a significantly better approximation ratio than the integrality gap for this problem {{harv|Feige|19961998}}.
Similar randomized rounding techniques, and derandomized approximation algorithms, may be used in conjunction with linear programming relaxation to develop approximation algorithms for many other problems, as described by Raghavan, Tompson, and Young.
==Branch and bound==
==References==
* {{citation | title=The relaxation method for linear inequalities | last=Agmon | first=Shmuel | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=382-392}}.
* {{citation | contributiontitle = A threshhold of ln ''n'' for approximating set cover | titlejournal = Proc.Journal of 28ththe ACM Symp.| Theoryyear of Computing= (STOC)1998 | yearpages = 1996634–652 |volume pages= 45 | issue = 312–3184 | last = Feige | first = U. | doi = 10.1145/285055.285059}}.
* {{citation | title = On the ratio of optimal integral and fractional covers | last = Lovász | first = Lászlo | journal = Discrete Mathematics | volume = 13 | pages = 383–390 | year = 1975 | doi = 10.1016/0012-365X(75)90058-8 }}.
* {{citation | title=The relaxation method for linear inequalities | last=Motzkin | first=TS | coauthors=IJ Schoenberg | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=393-404}}.
* {{citation | title= Randomized rounding: A technique for provably good algorithms and algorithmic proofs|first1=Prabhakar|last1=Raghavan|first2=Clark D. |last2=Tompson|journal=Combinatorica|volume=7|issue=4|year=1987|pages=365–374|doi=10.1007/BF02579324}}.
* {{citation | contribution = Randomized rounding without solving the linear program | first = Neal E. | last = Young | booktitle = Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA) | year = 1995 | url = http://portal.acm.org/citation.cfm?id=313689}}.
[[Category:Optimization]]
| 