Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 49:
* OPT(I) < 2*AVG(I), since in any packing with at least 2*AVG(I) bins, the sum of the two least-full bins is at most ''B'', so they can be combined into a single bin.
=== Rounding the fractional LP solution ===
Karmarkar and Karp<ref name=":12">{{cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=November 1982|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/document/4568405/references#references|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref> presented an algorithm for rounding an optimal solution for the fractional LP into a solution for the integral ILP, proving that OPT(I) ≤ FOPT(I) + S/2:
* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition, the value of '''x''' is FOPT(I). Since the fractional LP has ''S'' constraints, '''x''' has at most ''S'' nonzero variables, that is, at most ''S'' different configurations are used. We construct from '''x''' an integral packing consisting of a ''principal part'' and a ''residual part''.
Line 59 ⟶ 60:
* The execution time of this conversion algorithm is O(''n'' log ''n'').
=== Solving the fractional LP ===
Based on these lemmas, they present an algorithm with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.▼
A linear program with no integrality constraints can be solved in time polynomial in the number of variables and constraints. The problem is that the number of variables in the fractional configuration LP is equal to the number of possible configurations, which is exponential in 1/''e''. Karmarkar and Karp<ref name=":12" /> present an algorithm that runs in time polynomial in 1/''e.'' For any tolerance factor ''h'', their algorithm finds a basic feasible solution of cost at most FOPT(I) + ''h'', and runs in time:
<math>O\left(S^8 \log{S} \log^2(\frac{S n}{a h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{a h}) \right)</math>,
where ''S'' is the number of different sizes, ''n'' is the number of different items, and ''a'' is the size of the smallest item (divided by ''B''). A randomized variant of this algorithm runs in expected time:
<math>O\left(S^7 \log{S} \log^2(\frac{S n}{a h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{a h}) \right)</math>.
▲Based on these
=== Improvements ===
|