# 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

top## How 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.