Approximation schemes for packing with item fragmentation. (English) Zbl 1140.68548
Summary: We consider two variants of the classical bin packing problem in which items may be fragmented. This can potentially reduce the total number of bins needed for packing the instance. However, since fragmentation incurs overhead, we attempt to avoid it as much as possible. In Bin Packing with Size Increasing Fragmentation (BP-SIF), fragmenting an item increases the input size (due to a header/footer of fixed size that is added to each fragment). In bin packing with size preserving fragmentation (BP-SPF), there is a bound on the total number of fragmented items. These two variants of bin packing capture many practical scenarios, including message transmission in community TV networks, VLSI circuit design and preemptive scheduling on parallel machines with setup times/setup costs.
While both BP-SPF and BP-SIF do not belong to the class of problems that admit a Polynomial Time Approximation Scheme (PTAS), we show in this paper that both problems admit a dual PTAS and an asymptotic PTAS. We also develop for each of the problems a dual Asymptotic Fully Polynomial Time Approximation Scheme (AFPTAS). Our AFPTASs are based on a non-standard transformation of the mixed packing and covering linear program formulations of our problems into pure covering programs, which enables to efficiently solve these programs.
While both BP-SPF and BP-SIF do not belong to the class of problems that admit a Polynomial Time Approximation Scheme (PTAS), we show in this paper that both problems admit a dual PTAS and an asymptotic PTAS. We also develop for each of the problems a dual Asymptotic Fully Polynomial Time Approximation Scheme (AFPTAS). Our AFPTASs are based on a non-standard transformation of the mixed packing and covering linear program formulations of our problems into pure covering programs, which enables to efficiently solve these programs.
MSC:
| 68W25 | Approximation algorithms |
Keywords:
Polynomial time approximation schemes; Bin packing; Item fragmentation; Linear programming; AlgorithmsReferences:
| [1] | Beling, P., Megiddo, N.: Using fast matrix multiplication to find basic solutions. Theor. Comput. Sci. 205, 307–316 (1998) · Zbl 0913.68079 · doi:10.1016/S0304-3975(98)00003-6 |
| [2] | Braun, O., Schmidt, G.: Parallel processor scheduling with limited number of preemptions. SIAM J. Comput. 32(3), 671–680 (2003) · Zbl 1023.90021 · doi:10.1137/S0097539702410697 |
| [3] | Brucker, P.: Scheduling Algorithms, 4th edn. Springer, Berlin (2004) · Zbl 1060.90034 |
| [4] | Coffman, E.G. Jr., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing, Boston (1997) |
| [5] | Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press/McGraw–Hill, Cambridge/New York (2002) · Zbl 1187.68679 |
| [6] | Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. In: Proc. of the 7th European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 1643, pp. 151–162. Springer, Berlin (1999) · Zbl 0943.68010 |
| [7] | Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+{\(\epsilon\)} in linear time. Combinatorica 1, 349–355 (1981) · Zbl 0485.68057 · doi:10.1007/BF02579456 |
| [8] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979) · Zbl 0411.68039 |
| [9] | Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Practical and theoretical results. J. ACM 34(1), 144–162 (1987) · doi:10.1145/7531.7535 |
| [10] | Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–396 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150 |
| [11] | Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one dimensional bin packing problem. In: Proc. 23rd IEEE Annual Symposium on Foundations of Computer Science, pp. 312–320, 1982 |
| [12] | Leung, J.Y.-T. (ed.): Handbook of Scheduling: Algorithms, Models and Performance Analysis. Computer and Information Science Series. Chapman & Hall/CRC, Boca Raton (2004) |
| [13] | Mandal, C.A., Chakrabarti, P.P., Ghose, S.: Complexity of fragmentable object bin packing and an application. Comp. Math. Appl. 35(11), 91–97 (1998) · Zbl 0992.90058 · doi:10.1016/S0898-1221(98)00087-X |
| [14] | McNaughton, R.: Scheduling with deadlines and loss functions. Manag. Sci. 6, 1–12 (1959) · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1 |
| [15] | Menakerman, N., Rom, R.: Bin packing problems with item fragmentations. In: Proc. of WADS, 2001 · Zbl 0997.68526 |
| [16] | Motwani, R.: Lecture notes on approximation algorithms. Technical report, Dept. of Computer Science, Stanford Univ., CA (1992) |
| [17] | Multimedia Cable Network System Ltd.: Data-over-cable service interface specification, http://www.cablelabs.com (2000) |
| [18] | Naaman, N., Rom, R.: Packet scheduling with fragmentation. In: Proc. of INFOCOM’02, pp. 824–831, 2002 |
| [19] | Shachnai, H., Tamir, T., Woeginger, G.J.: Minimizing makespan and preemption costs on a system of uniform machines. Algorithmica 42, 309–334 (2005) · Zbl 1086.90028 · doi:10.1007/s00453-005-1171-0 |
| [20] | Sourd, F.: Preemptive scheduling with position costs. Algorithmic Oper. Res. AOR 1(2) (2006) · Zbl 1186.90121 |
| [21] | Spielman, D.A., Teng, S.-H.: Smoothed analysis of termination of linear programming algorithms. Math. Program. Ser. B 97, 375–404 (2003) · Zbl 1035.90042 |
| [22] | Todd, M.J.: The many facets of linear programming. Math. Program. Ser. B 91, 417–436 (2002) · Zbl 1030.90051 · doi:10.1007/s101070100261 |
| [23] | Vazirani, V.V.: Bin packing. In: Approximation Algorithms, pp. 74–78. Springer, Berlin (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
