Content deleted Content added
Alter: template type. Add: pages, date, chapter, title. | Use this tool. Report bugs. | #UCB_Gadget | Add: volume, series, chapter, url, title. Removed proxy/dead URL that duplicated identifier. | Use this tool. Report bugs. | #UCB_Gadget |
ce |
||
Line 50:
== In bin covering ==
In the [[bin packing|bin covering problem]], there are ''n'' items with different sizes. The goal is to pack the items into a ''maximum'' number of bins, where each bin should contain ''at least'' ''B''. A natural configuration LP for this problem could be:<blockquote><math>\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\leq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>where '''''A''''' represents all configurations of items with sum ''at least'' ''B'' (one can take only the inclusion-minimal configurations). The problem with this LP is that, in the bin-covering problem, handling small items is problematic, since small items may be essential for the optimal solution. With small items allowed, the number of configurations may be too large even for the technique of Karmarkar and Karp. Csirik, Johnson and Kenyon<ref name=":24">{{Cite book|last1=Csirik|first1=Janos|last2=Johnson|first2=David S.|last3=Kenyon|first3=Claire|chapter=Better approximation algorithms for bin covering |date=2001-01-09 |chapter-url=https://dl.acm.org/doi/abs/10.5555/365411.365533 |title=SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms |publisher=Society for Industrial and Applied Mathematics |pages=557–566|isbn=978-0-89871-490-6}}</ref> present an alternative LP. First, they define a set of items that are called ''small''. Let ''T'' be the total size of all small items. Then, they construct a matrix '''A''' representing all configurations with sum < 2. Then, they consider the above LP with one additional constraint:<math display="block">\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~\text{s.t.}</math><math display="block">A \mathbf{x}\leq \mathbf{n}</math><math display="block">\sum_{c\in C: sum(c)<B} (B-sum(c))\cdot x_c \leq T</math><math display="block">\mathbf{x}\geq 0</math>The additional constraint guarantees that the "vacant space" in the bins can be filled by the small items. The dual of this LP is more complex and cannot be solved by a simple knapsack-problem separation oracle. Csirik, Johnson and Kenyon<ref name=":24" /> present a different method to solve it approximately in time exponential in 1/epsilon. Jansen and Solis-Oba'''<ref name=":32">{{Cite book|last1=Jansen|first1=Klaus|last2=Solis-Oba|first2=Roberto|title=Algorithms and Computation |chapter=An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering |series=Lecture Notes in Computer Science |date=2002-11-21 |volume=2518 |chapter-url=https://dl.acm.org/doi/abs/10.5555/646345.689912 |publisher=Springer-Verlag |pages=175–186|doi=10.1007/3-540-36136-7_16|isbn=978-3-540-00142-3}}</ref>''' present an improved method to solve it approximately in time exponential in 1/epsilon.
== In machine scheduling ==
| |||