Parallel approximation algorithms for bin packing. (English) Zbl 0677.90054

Anderson, Richard J.; Mayr, Ernst W.; Warmuth, Manfred K.

Inf. Comput. 82, No. 3, 262-277 (1989).

Summary: We study the parallel complexity of polynomial heuristics for the bin packing problem. We show that some well-known (and simple) methods like first-fit-decreasing are \({\mathcal P}\)-complete, and it is hence very unlikely that they can be efficiently parallelized. On the other hand, we exhibit an optimal \({\mathcal N}{\mathcal C}\) algorithm that achieves the same performance bound as does FFD. Finally, we discuss parallelization of polynomial approximation algorithms for bin packing based on discretization.

MSC:

90C27	Combinatorial optimization
65K05	Numerical mathematical programming methods
68N25	Theory of operating systems
65Y05	Parallel numerical computation
68Q25	Analysis of algorithms and problem complexity

Keywords:

parallel complexity of polynomial heuristics; bin packing; polynomial approximation algorithms

References:

[1]	Anderson, R.; Mayr, E., Parallelism and greedy algorithms, (Preparata, F. P., Advances in Computng Research; Parallel and Distrubuted Computing (1987), JAI Press: JAI Press Greenwich, CT), 17-38
[2]	Baker, B., A new proof for the first-fit decreasing bin-packing algorithm, J. Algorithms, 6, No. 1, 49-70 (1985) · Zbl 0563.68042
[3]	Bar-On, I.; Vishkin, U., Optimal parallel generation of a computation tree form, ACM Trans. Programming Lang. Systems, 7, No. 2, 348-357 (1985) · Zbl 0564.68037
[4]	Batcher, K., Sorting networks and their applications, (Proceedings, AFIPS Spring Joint Comput. Conf. (1968)), 307-314
[5]	Dobkin, D.; Lipton, R.; Reiss, S., Linear programming is log-space hard forP, Inform. Process. Lett., 8, No. 2, 96-97 (1979) · Zbl 0402.68042
[6]	Fernandez de la Vega, W.; Lueker, G., Bin packing can be solved within 1 + ɛ in linear time, Combinatorica, 1, No. 4, 349-355 (1981) · Zbl 0485.68057
[7]	Fortune, S.; Wyllie, J., Parallelism in random access machines, (Proceedings, 10th Ann. ACM Symposium on Theory of Computing. Proceedings, 10th Ann. ACM Symposium on Theory of Computing, San Diego, CA (1978), Assoc. Comput. Mach.: Assoc. Comput. Mach. New York), 114-118 · Zbl 1282.68104
[8]	Goldschlager, L.; Shaw, R.; Staples, J., The maximum flow problem is log space complete forP, Theoret. Comput. Sci., 21, No. 21, 105-111 (1982) · Zbl 0486.68035
[9]	Helmhold, D.; Mayr, E., Fast scheduling algorithms on parallel computers, (Preparata, F. P., Advances in Computing Research; Parallel and Distributed Computing (1987), JAI Press: JAI Press Greenwich, CT), 39-68
[10]	Johnson, D.; Demers, A.; Ullman, J.; Garey, M.; Graham, R., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput., 3, 299-326 (1974) · Zbl 0297.68028
[11]	Karmarkar, N.; Karp, R., An efficient approximation scheme for the one-dimensional bin-packing problem, (Proceedings, 23rd Ann. IEEE Symposium on Foundations of Computer Science. Proceedings, 23rd Ann. IEEE Symposium on Foundations of Computer Science, Chicago, IL (1982), IEEE: IEEE New York), 312-320
[12]	Karp, R.; Upfal, E.; Wigderson, A., Constructing a perfect matching is in randomNC, (Proceedings, 17th Ann. ACM Symposium on Theory of Computing. Proceedings, 17th Ann. ACM Symposium on Theory of Computing, Providence, RI (1985), ACM: ACM New York), 22-32
[13]	Ladner, R., The circuit value problem is log-space complete forP, SIGACT News, 7, 1, 553-590 (1975)
[14]	Ladner, R.; Fischer, M., Parallel prefix computation, Assoc. Comput. Mach., 27, No. 4, 831-838 (1980) · Zbl 0445.68066
[15]	Pippenger, N., On simultaneous resource bounds, (Proceedings, 20th Ann. IEEE Symposium on Foundations of Computer Science. Proceedings, 20th Ann. IEEE Symposium on Foundations of Computer Science, San Juan, PR (1979), IEEE: IEEE New York), 307-311
[16]	Stone, H., Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, No. 2, 163-271 (1971) · Zbl 0214.42703