Worst case analysis of two heuristics for the set partitioning problem. (English) Zbl 0635.68030
We propose and analyze two simple heuristics for the problem of partitioning a set that use few steps of enumeration. We show that the new heuristics have a significantly better worst case ratio than previously known heuristics.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68P10 | Searching and sorting |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | M. FISCHETTI and S. MARTELLO, Worst-Case Analysis of the Differencing Method for the Partition Problem, Internal Report University of Bologna, 1986. MR881698 · Zbl 0609.90094 |
| [2] | 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. MR522459 · Zbl 0388.90032 |
| [3] | D. S. JOHNSON, Approximation Algorithms for Combinatorial Problem 2, Journal of Computer and System Sciences, Vol. 9, 1974, pp. 256-278. MR449012 · Zbl 0296.65036 |
| [4] | N. KARMARKAR and R. M. KARP, The Differencing Method of Set Partitioning, Mathematics of Operations Research (to appear). |
| [5] | R. M. KARP, R. E. MILLER and J. W. THATCHER, Reducibility Among Combinatorial Problems, Complexity of Computer Computation, Plenum Press, N.Y., 1972. Zbl0366.68041 MR378476 · Zbl 0366.68041 |
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.
