Worst case analysis of two heuristics for the set partitioning problem
A. Marchetti Spaccamela; A. Pelaggi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1987)
- Volume: 21, Issue: 1, page 11-23
- ISSN: 0988-3754
Access Full Article
topHow to cite
topMarchetti Spaccamela, A., and Pelaggi, A.. "Worst case analysis of two heuristics for the set partitioning problem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 21.1 (1987): 11-23. <http://eudml.org/doc/92274>.
@article{MarchettiSpaccamela1987,
author = {Marchetti Spaccamela, A., Pelaggi, A.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {set partitioning problem; scheduling},
language = {eng},
number = {1},
pages = {11-23},
publisher = {EDP-Sciences},
title = {Worst case analysis of two heuristics for the set partitioning problem},
url = {http://eudml.org/doc/92274},
volume = {21},
year = {1987},
}
TY - JOUR
AU - Marchetti Spaccamela, A.
AU - Pelaggi, A.
TI - Worst case analysis of two heuristics for the set partitioning problem
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1987
PB - EDP-Sciences
VL - 21
IS - 1
SP - 11
EP - 23
LA - eng
KW - set partitioning problem; scheduling
UR - http://eudml.org/doc/92274
ER -
References
top- [FM] M. FISCHETTI and S. MARTELLO, Worst-Case Analysis of the Differencing Method for the Partition Problem, Internal Report University of Bologna, 1986. MR881698
- [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. Zbl0388.90032MR522459
- [J] D. S. JOHNSON, Approximation Algorithms for Combinatorial Problem 2, Journal of Computer and System Sciences, Vol. 9, 1974, pp. 256-278. Zbl0296.65036MR449012
- [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. Zbl0366.68041MR378476
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.