{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T17:50:18Z","timestamp":1775325018740,"version":"3.50.1"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1979,6,1]],"date-time":"1979-06-01T00:00:00Z","timestamp":297043200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Zeitschrift f\u00fcr Operations Research"],"published-print":{"date-parts":[[1979,6]]},"DOI":"10.1007\/bf01951543","type":"journal-article","created":{"date-parts":[[2005,7,30]],"date-time":"2005-07-30T22:36:33Z","timestamp":1122762993000},"page":"73-94","source":"Crossref","is-referenced-by-count":8,"title":["NP-Complete operations research problems and approximation algorithms"],"prefix":"10.1007","volume":"23","author":[{"given":"Peter","family":"Brucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01951543_CR1","unstructured":"Aho, A., J. Hopcroft, andJ. Ullman: The Design and Analysis for Computer Algorithms. Reading, Mass. 1974."},{"key":"BF01951543_CR2","unstructured":"Brucker, P.: NP-vollst\u00e4ndige Operations Research Probleme. Graphen, Algorithmen, Datenstrukturen. Ed. by H. Noltemeier. M\u00fcnchen 1976."},{"key":"BF01951543_CR3","doi-asserted-by":"crossref","unstructured":"-: On the Complexity of Clustering Problems. Optimization and Operations Research. Ed. by R. Henn, B. Korte, and W. Oettli. Berlin 1978.","DOI":"10.1007\/978-3-642-95322-4"},{"key":"BF01951543_CR4","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1287\/moor.2.3.275","volume":"2","author":"P. Brucker","year":"1977","unstructured":"Brucker, P., M. Garey, andD. Johnson: Scheduling Equal Length Tasks under Tree Like Precedence Constraints to Minimize Maximum Lateness. Math. of Operations Research2, 1977, 275\u2013284. 275\u2013284.","journal-title":"Math. of Operations Research"},{"key":"BF01951543_CR5","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1145\/361011.361064","volume":"17","author":"J. Bruno","year":"1974","unstructured":"Bruno, J., E.G. Coffman Jr., andR. Sethi: Scheduling Independent Tasks to Recue Mean Finishing-Time. Comm. ACM17, 1974, 504\u2013510.","journal-title":"Comm. ACM"},{"key":"BF01951543_CR6","unstructured":"Christofides, N.: Worst Case Analysis of a New Heuristic for the Traveling Salesman Problem. Management Sci. Res. Report No. 388, Carnegie Mellon University 1976."},{"key":"BF01951543_CR7","unstructured":"Coffman, E.G., Jr.: Computer and Job-Shop Scheduling Theory. New York 1976."},{"key":"BF01951543_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"E. Coffman","year":"1978","unstructured":"Coffman, E., M. Garey, andD. Johnson: An Application of Bin-Packing to Multiprocessor Scheduling. Siam J. Computing7, 1978, 1\u201317.","journal-title":"Siam J. Computing"},{"key":"BF01951543_CR9","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF01951543_CR10","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G. Cornuejols","year":"1977","unstructured":"Cornuejols, G., M. Fisher, andG. Nemhauser: Location of Bank accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Science23, 1977, 789\u2013810.","journal-title":"Management Science"},{"key":"BF01951543_CR11","unstructured":"Dahl, O.J., E.W. Dijkstra, andC.A.R. Hoare: Structured Programming. New York 1972."},{"key":"BF01951543_CR12","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"Even, S., A. Itai, andA. Shamir: On the Complexity of a Timetable and Multicommodity Flow Problems. SIAM J. Comput.5, 1976, 691\u2013703.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR13","unstructured":"Fisher, M., G. Nemhauser, andL. Wolsey: An Analysis of Approximations for Finding a Maximum Weight Hamilton Circuit. To appear in Operations Research."},{"key":"BF01951543_CR14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"M. Garey","year":"1975","unstructured":"Garey, M., andR. Graham: Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM J. Comput.4, 1975, 187\u2013200.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR15","doi-asserted-by":"crossref","unstructured":"Garey, M., R. Graham, andD. Johnson: SomeNP-complete Geometric Problems. Proceedings of 8th Annual ACM Symposium on Theory of Computing, 1976, 10\u201322.","DOI":"10.1145\/800113.803626"},{"key":"BF01951543_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/opre.26.1.3","volume":"26","author":"M. Garey","year":"1978","unstructured":"\u2014: Performance Guarantees for Scheduling Algorithms. Operations Research26, 1978, 3\u201321.","journal-title":"Operations Research"},{"key":"BF01951543_CR17","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"M. Garey","year":"1975","unstructured":"Garey, M., andD. Johnson: Complexity Results for Multiprocessor Scheduling under Resource Contraints. SIAM J. Comput.4, 1975, 397\u2013411.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR18","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/321958.321967","volume":"23","author":"M. Garey","year":"1976","unstructured":"\u2014: Scheduling Tasks with Nonuniform Deadlines on two Processors. J. ACM23, 1976, 461\u2013467.","journal-title":"J. ACM"},{"key":"BF01951543_CR19","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M. Garey","year":"1978","unstructured":"\u2014: StrongNP-Completeness Results: Motiviation, Examples and Implications. J. ACM25, 1978, 499\u2013508.","journal-title":"J. ACM"},{"key":"BF01951543_CR20","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., D. Johnson, andR. Sethi: The Complexity of Flowshop and Jobshop scheduling. Math. Operations Research1, 1976, 117\u2013129.","journal-title":"Math. Operations Research"},{"key":"BF01951543_CR21","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., D. Johnson, andL. Stockmeyer: Some SimplifiedNP-Complete Problems. J. Theory Comput. Sci.1, 1976, 237\u2013267.","journal-title":"J. Theory Comput. Sci."},{"key":"BF01951543_CR22","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. Garey","year":"1976","unstructured":"Garey, M., D. Johnson, andR. Tarjan: The Planar Hamilton Circuit Problem isNP-Complete. SIAM J. Comput.5, 1976, 704\u2013714.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR23","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1137\/0206013","volume":"6","author":"T. Gonzales","year":"1977","unstructured":"Gonzales, T., O. Ibarra, andS. Sahni: Bounds for LPT Schedules on Uniform Processors. SIAM J. Comput.6, 1977, 155\u2013166.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR24","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T. Gonzales","year":"1976","unstructured":"Gonzales, T., andS. Sahni: Open Shop Scheduling to Minimize Finish Time. J. ACM23, 1976, 665\u2013679.","journal-title":"J. ACM"},{"key":"BF01951543_CR25","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/opre.26.1.36","volume":"26","author":"T. Gonzales","year":"1978","unstructured":"\u2014: Flowshop and Jobshop Schedules: Complexity and Approximation. Operations Research26, 1978, 36\u201352.","journal-title":"Operations Research"},{"key":"BF01951543_CR26","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. Graham","year":"1966","unstructured":"Graham, R.: Bounds for Certain Multiprocessing Anomalies. Bell System Techn. J.45, 1966, 1563\u20131581.","journal-title":"Bell System Techn. J."},{"key":"BF01951543_CR27","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R. Graham","year":"1969","unstructured":"\u2014: Bounds for Multiprocessing Timing Anomalies. SIAM J. Appl. Math.17, 1969, 416\u2013429.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01951543_CR28","unstructured":"-: Bounds on the Performance of Scheduling Algorithms. Computer and Job-Shop Scheduling Theory. Ed. by E. Coffman Jr. New York 1976."},{"key":"BF01951543_CR29","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., andS. Sahni: Exact and Approximate Algorithms for Scheduling Nonidentical Processors. J. ACM23, 1976, 317\u2013327.","journal-title":"J. ACM"},{"key":"BF01951543_CR30","volume-title":"Fundamentals of Computer Algorithms","author":"E. Horowitz","year":"1978","unstructured":"\u2014: Fundamentals of Computer Algorithms. Computer Science Press, Pontomac, Md. 1978."},{"key":"BF01951543_CR31","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/321992.321995","volume":"24","author":"E. Horvath","year":"1977","unstructured":"Horvath, E., S. Lam, andR. Sethi: A Level Algorithm for Preemptive Scheduling. J. ACM24, 1977, 32\u201343.","journal-title":"J. ACM"},{"key":"BF01951543_CR32","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/322092.322100","volume":"25","author":"A. Itai","year":"1978","unstructured":"Itai, A.: Two Commodity Flow. J. ACM25, 1978, 596\u2013611.","journal-title":"J. ACM"},{"key":"BF01951543_CR33","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/322092.322100","volume":"25","author":"A. Itai","year":"1978","unstructured":"Itai, A., M. Rodeh, andS.L. Tanimoto: Some Matching Problems for Bipartite Graphs. J. ACM25, 1978, 517\u2013525.","journal-title":"J. ACM"},{"key":"BF01951543_CR34","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. Ibarra","year":"1975","unstructured":"Ibarra, O., andC. Kim: Fast Approximation Algorithms for the Knapsack and Sum of Subsets Problems. J. ACM22, 1975, 463\u2013468.","journal-title":"J. ACM"},{"key":"BF01951543_CR35","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/322003.322011","volume":"24","author":"O. Ibarra","year":"1977","unstructured":"\u2014: Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors. J. ACM24, 1977, 280\u2013289.","journal-title":"J. ACM"},{"key":"BF01951543_CR36","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1287\/moor.3.3.197","volume":"3","author":"O. Ibarra","year":"1978","unstructured":"\u2014: Approximation Algorithms for Certain Scheduling Problems, Math. Operations Research3, 1978, 197\u2013204.","journal-title":"Math. Operations Research"},{"key":"BF01951543_CR37","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Fast Algorithms for Bin Packing. J. Comput. System Sci.8, 1974, 272\u2013314.","journal-title":"J. Comput. System Sci."},{"key":"BF01951543_CR38","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"D. Johnson","year":"1974","unstructured":"Johnson, D., A. Demers, J. Ullman, M. Garey, andR. Graham: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput.3, 1974, 299\u2013325.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR39","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among Combinatorial Problems. Complexity of Computer Computations. Ed. by R.E. Miller, and J.W. Thatcher. New York 1972, 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"BF01951543_CR40","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. Karp","year":"1975","unstructured":"\u2014: On the Computational Complexity of Combinatorial Problems. Networks5, 1975, 45\u201368.","journal-title":"Networks"},{"key":"BF01951543_CR41","unstructured":"-: The Probabilistic Analysis of Some Combinatorial Search Algorithms. Ed. by J. Traub. Algorithms and Complexity: New Directions and Recent Results. New York 1976, 1\u201320."},{"key":"BF01951543_CR42","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R. Karp","year":"1977","unstructured":"\u2014: Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plane. Math. Operations Research2, 1977, 209\u2013224.","journal-title":"Math. Operations Research"},{"key":"BF01951543_CR43","volume-title":"Memorandum No. UCB\/ERL M 78\/2","author":"R. Karp","year":"1978","unstructured":"\u2014: A Patching Algorithm for the Nonsymetric Traveling Salesman Problem. Memorandum No. UCB\/ERL M 78\/2, University of California, Berkely, 1978."},{"key":"BF01951543_CR44","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1109\/T-C.1974.223825","volume":"C-23","author":"M. Kaufman","year":"1974","unstructured":"Kaufman, M.: An Almost-Optimal Algorithm for the Assembly Line Scheduling Problem. IEEE Trans. Comput. C-23, 1974, 1169\u20131174.","journal-title":"IEEE Trans. Comput."},{"key":"BF01951543_CR45","unstructured":"Kim, C.: Analysis of the Expected Performance of Algorithms for the Partition Problem. University of Maryland, Computer Science Technical Report, 1976."},{"key":"BF01951543_CR46","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/356635.356640","volume":"6","author":"D. Knuth","year":"1974","unstructured":"Knuth, D.: Structured Programming with Go To's. ACM Surveys6, 1974, 261\u2013302.","journal-title":"ACM Surveys"},{"key":"BF01951543_CR47","doi-asserted-by":"crossref","unstructured":"Lawler, E.: Fast Approximation Algorithms for Knapsack Problems. Proceedings, 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, 1977, 206\u2013213.","DOI":"10.1109\/SFCS.1977.11"},{"key":"BF01951543_CR48","unstructured":"-: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints. Ann. Discrete Math. to appear."},{"key":"BF01951543_CR49","volume-title":"Ph. D. thesis","author":"J.K. Lenstra","year":"1976","unstructured":"Lenstra, J.K.: Sequencing by Enumerative Methods. Ph. D. thesis, Mathematisch Centrum, Amsterdam 1976."},{"key":"BF01951543_CR50","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., A.H.G. Rinnooy Kan: Complexity of Scheduling under Precedence Constraints. Operations Research26, 1978, 22\u201335.","journal-title":"Operations Research"},{"key":"BF01951543_CR51","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J.K. Lenstra","year":"1977","unstructured":"Lenstra, J.K., A.H. G. Rinnooy Kan, andP. Brucker: Complexity of Machine Scheduling Problems. Ann. Discrete Math.1, 1977, 343\u2013362.","journal-title":"Ann. Discrete Math."},{"key":"BF01951543_CR52","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., andP. Kernighan: An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research21, 1973, 498\u2013516.","journal-title":"Operations Research"},{"key":"BF01951543_CR53","unstructured":"Mehlhorn, K.: Effiziente Algorithmen. Stuttgart 1977."},{"key":"BF01951543_CR54","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G. Nemhauser","year":"1978","unstructured":"Nemhauser, G., andL. Wolsey: Best Algorithms for Approximating the Maximum of a Sub-modular Set Function. Math. Operations Research3, 1978, 177\u2013188.","journal-title":"Math. Operations Research"},{"key":"BF01951543_CR55","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., andK. Steiglitz: Some Complexity Results for the Traveling Salesman Problem. Proceedings 8th Annual ACM Symposium on Theory of Computing, 1976, 1\u20139.","DOI":"10.1145\/800113.803625"},{"key":"BF01951543_CR56","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. Posa","year":"1976","unstructured":"Posa, L.: Hamiltonian Circuits in Random Graphs. Discrete Math.14, 1976, 359\u2013369.","journal-title":"Discrete Math."},{"key":"BF01951543_CR57","unstructured":"Rinnooy Kan, A.H.G.: Machine Scheduling Problems: Classification, Complexity and Computations. The Hague 1976."},{"key":"BF01951543_CR58","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S. Sahni","year":"1974","unstructured":"Sahni, S.: Computationally Related Problems. SIAM J. Comput.3, 1974, 262\u2013279.","journal-title":"SIAM J. Comput."},{"key":"BF01951543_CR59","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S. Sahni","year":"1975","unstructured":"\u2014: Approximate Algorithms for the 0\/1 Knapsack Problem. J. ACM22, 1975, 115\u2013124.","journal-title":"J. ACM"},{"key":"BF01951543_CR60","first-page":"114","volume":"23","author":"S. Sahni","year":"1976","unstructured":"\u2014: Algorithms for Scheduling Independent Tasks, J. ACM23, 1976, 114\u2013127.","journal-title":"J. ACM"},{"key":"BF01951543_CR61","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1287\/opre.25.6.920","volume":"25","author":"S. Sahni","year":"1977","unstructured":"\u2014: General Techniques for Combinatorial Approximation. Operations Research25, 1977, 920\u2013936.","journal-title":"Operations Research"},{"key":"BF01951543_CR62","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1287\/opre.26.5.718","volume":"5","author":"S. Sahni","year":"1978","unstructured":"Sahni, S., andE. Horowitz: Combinatorial Problems: Reducibility and Approximation. Operations Research5, 1978, 718\u2013759.","journal-title":"Operations Research"},{"key":"BF01951543_CR63","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: Complexity of Decision Problems Based on Finite Two-Person Perfect-Information Games. Proceedings 8th Annual ACM Symposium on Theory of Computing, 1976, 41\u201349.","DOI":"10.1145\/800113.803629"},{"key":"BF01951543_CR64","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/moor.2.4.320","volume":"2","author":"R. Sethi","year":"1977","unstructured":"Sethi, R.: On the Complexity of Mean Flow Time Scheduling. Math. Operations Research2, 1977, 320\u2013330.","journal-title":"Math. Operations Research"},{"key":"BF01951543_CR65","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J.D. Ullman","year":"1975","unstructured":"Ullman, J.D.: NP-Complete Scheduling Problems, J. Comput. Syst. Sci.10, 1975, 384\u2013393.","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Zeitschrift f\u00fcr Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01951543.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01951543\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01951543","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T13:09:29Z","timestamp":1586351369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01951543"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,6]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1979,6]]}},"alternative-id":["BF01951543"],"URL":"https:\/\/doi.org\/10.1007\/bf01951543","relation":{},"ISSN":["0340-9422","1432-5217"],"issn-type":[{"value":"0340-9422","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,6]]}}}