×

Performance ratios for the Karmarkar-Karp differencing method. (English) Zbl 1075.68560

Extended abstracts of the 2nd Cologne Twente workshop on graphs and combinatorial optimization, Enschede, Netherlands, May 14–16, 2003. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 13, 71-75 (2003).
For the entire collection see [Zbl 1074.05002].

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Jr., E. G. Coffman; Frederickson, G. N.; Lueker, G. S.: A note on expected makespans for largest-first sequences of independent tasks on two processors. Mathematics of operations research 9, 260-266 (1984) · Zbl 0538.90036
[2] Jr, E. G. Coffman; Garey, M. R.; Johnson, D. S.: An application of bin-packing to multiprocessor scheduling. SIAM journal on computing 7, No. 1, 1-17 (1978) · Zbl 0374.68032
[3] Jr., E. G. Coffman; Whitt, W.: Recent asymptotic results in the probabilistic analysis of schedule makespans. Scheduling theory and its applications, 15-31 (1995)
[4] Fischetti, M.; Martello, S.: Worst-case analysis of the differencing method for the partition problem. Mathematical programming 37, 117-120 (1987) · Zbl 0609.90094
[5] Frenk, J. B. G.; Kan, A. H. G. Rinnooy: The rate of convergence to optimality of the LPT rule. Discrete applied mathematics 14, 187-197 (1986) · Zbl 0611.90058
[6] Friesen, D. K.: Tighter bounds for the multifit processor scheduling algorithm. SIAM journal on computing 13, No. 1, 170-181 (1984) · Zbl 0539.68024
[7] Garey, M. R.; Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness. (1979) · Zbl 0411.68039
[8] Graham, R. L.: Bounds on multiprocessing timing anomalies. SIAM journal on applied mathematics 17, No. 2, 416-429 (1969) · Zbl 0188.23101
[9] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy, A. H. G. Kan: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of discrete mathematics 5, 287-326 (1979) · Zbl 0411.90044
[10] Hochbaum, D. S.; Shmoys, D. B.: Using dual approximation algorithms for scheduling problems: thoretical and practical results. Journal of the ACM 34, 144-162 (1987)
[11] N. Karmarkar and R. M. Karp. The differencing method of set partitioning. Technical Report UCB/CSD 82/113, University of California, Berkeley, 1982.
[12] Korf, R. E.: A complete anytime algorithm for number partitioning. Artificial intelligence 106, 181-203 (1998) · Zbl 0910.68084
[13] Lueker, G. S.: A note on the average-case behavior of a simple differencing method for partitioning. Operations research letters 6, No. 6, 285-287 (1987) · Zbl 0631.90053
[14] S. Mertens. A complete anytime algorithm for balanced number partitioning, 1999. preprint xxx.lanl.gov/abs/cs.DS/9903011.
[15] Ruml, W.; Ngo, J. T.; Marks, J.; Shieber, S.: Easily searched encodings for number partitioning. Journal of optimization theory and applications 89, No. 2, 251-291 (1996) · Zbl 0853.90096
[16] Storer, R. H.; Flanders, S. W.; Wu, S. D.: Problem space local search for number partitioning. Annals of operations research 63, 465-487 (1996) · Zbl 0851.90100
[17] Tasi, L. H.: The modified differencing method for the set partitioning problem with cardinality constraints. Discrete applied mathematics 63, 175-180 (1995) · Zbl 0837.90105
[18] Tsai, L. H.: Asymptotic analysis of an algorithm for balanced parallel processor scheduling. SIAM journal on computing 21, No. 1, 59-64 (1992) · Zbl 0743.68081
[19] Yakir, B.: The differencing algorithm LDM for partitioning: A proof of karp’s conjecture. Mathematics of operations research 21, No. 1, 85-99 (1996) · Zbl 0846.90057
[20] Yue, M.: On the exact upper bound for the multifit processor scheduling algorithm. Annals of operations research 24, 233-259 (1990) · Zbl 0708.90042
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.