Worst case analysis of two heuristics for the set partitioning problem
Marchetti Spaccamela, A. ; Pelaggi, A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987), p. 11-23 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1987-01-01
@article{ITA_1987__21_1_11_0,
     author = {Marchetti Spaccamela, A. and Pelaggi, A.},
     title = {Worst case analysis of two heuristics for the set partitioning problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {21},
     year = {1987},
     pages = {11-23},
     mrnumber = {882867},
     zbl = {0635.68030},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1987__21_1_11_0}
}

Marchetti Spaccamela, A.; Pelaggi, A. Worst case analysis of two heuristics for the set partitioning problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) pp. 11-23. http://gdmltest.u-ga.fr/item/ITA_1987__21_1_11_0/

[FM] M. Fischetti and S. Martello, Worst-Case Analysis of the Differencing Method for the Partition Problem, Internal Report University of Bologna, 1986. | MR 881698

[G] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. K. G. Rinnooy Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling : a Survey, Ann. Discrete Math., 1978. | MR 522459

[J] D. S. Johnson, Approximation Algorithms for Combinatorial Problem 2, Journal of Computer and System Sciences, Vol. 9, 1974, pp. 256-278. | MR 449012

[KK] N. Karmarkar and R. M. Karp, The Differencing Method of Set Partitioning, Mathematics of Operations Research (to appear).

[K] R. M. Karp, R. E. Miller and J. W. Thatcher, Reducibility Among Combinatorial Problems, Complexity of Computer Computation, Plenum Press, N.Y., 1972. | MR 378476 | Zbl 0366.68041