{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T08:09:48Z","timestamp":1745309388826},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1993,5,1]],"date-time":"1993-05-01T00:00:00Z","timestamp":736214400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1993,5]]},"DOI":"10.1007\/bf02025297","type":"journal-article","created":{"date-parts":[[2005,8,10]],"date-time":"2005-08-10T12:48:16Z","timestamp":1123678096000},"page":"259-277","source":"Crossref","is-referenced-by-count":12,"title":["Algorithms for large scale set covering problems"],"prefix":"10.1007","volume":"43","author":[{"given":"N.","family":"Christofides","sequence":"first","affiliation":[]},{"given":"J.","family":"Paix\u00e3o","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02025297_CR1","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0377-2217(89)90471-2","volume":"38","author":"A.I. Ali","year":"1989","unstructured":"A.I. Ali and H. Thiagarajan, A network relaxation based enumeration algorithm for set partitioning, Eur. J. Oper. Res. 38(1989)76\u201385.","journal-title":"Eur. J. Oper. Res."},{"key":"BF02025297_CR2","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1287\/trsc.3.2.140","volume":"3","author":"J.P. Arabeyre","year":"1969","unstructured":"J.P. Arabeyre, J. Fearnley, F.C. Steiger and W. Teather, The airline crew scheduling problem: a survey, Transp. Sci. 3(1969)140\u2013163.","journal-title":"Transp. Sci."},{"key":"BF02025297_CR3","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0305-0548(81)90017-4","volume":"8","author":"E. Baker","year":"1981","unstructured":"E. Baker, Efficient heuristic algorithms for the weighted set covering problem, Comp. Oper. Res. 8(1981)303\u2013310.","journal-title":"Comp. Oper. Res."},{"key":"BF02025297_CR4","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/0305-0483(81)90049-9","volume":"9","author":"E. Baker","year":"1981","unstructured":"E. Baker and M. Fisher, Computational results for very large air crew scheduling problems, Omega 9(1981)613\u2013618.","journal-title":"Omega"},{"key":"BF02025297_CR5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BFb0120885","volume":"12","author":"E. Balas","year":"1980","unstructured":"E. Balas, Cutting planes from conditional bounds: a new approach for set covering, Math. Progr. Study 12(1980)19\u201336.","journal-title":"Math. Progr. Study"},{"key":"BF02025297_CR6","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BFb0120886","volume":"12","author":"E. Balas","year":"1980","unstructured":"E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics and subgradient optimization: a computational study, Math. Progr. Study 12(1980)37\u201360.","journal-title":"Math. Progr. Study"},{"key":"BF02025297_CR7","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1137\/1018115","volume":"18","author":"E. Balas","year":"1976","unstructured":"E. Balas and M.W. Padberg, Set partitioning: a survey, SIAM Rev. 18(1976)710\u2013760.","journal-title":"SIAM Rev."},{"key":"BF02025297_CR8","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1287\/opre.12.2.300","volume":"12","author":"M.L. Balinski","year":"1964","unstructured":"M.L. Balinski and R.E. Quandt, On an integer program for a delivery problem, Oper. Res. 12(1964)300\u2013304.","journal-title":"Oper. Res."},{"key":"BF02025297_CR9","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1287\/mnsc.36.1.16","volume":"36","author":"R. Batta","year":"1990","unstructured":"R. Batta and N. Mannur, Covering-location models for emergency situations that require multiple response units, Manag. Sci. 36(1990)16\u201323.","journal-title":"Manag. Sci."},{"key":"BF02025297_CR10","first-page":"501","volume":"31","author":"J.E. Beasley","year":"1983","unstructured":"J.E. Beasley, An algorithm for set covering problems, Eur. J. Oper. Res. 31(1983)501\u2013510.","journal-title":"Eur. J. Oper. Res."},{"key":"BF02025297_CR11","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1287\/mnsc.18.4.B174","volume":"18","author":"M. Belmore","year":"1971","unstructured":"M. Belmore and H.D. Ratliff, Optimal defence of multi-commodity networks, Manag. Sci. 18(1971)174\u2013185.","journal-title":"Manag. Sci."},{"key":"BF02025297_CR12","unstructured":"J. Bouliane and G. Laporte, Locating postal relay boxes using a set covering algorithm, Centre de Recherche sur les Transports, Publication #611, Universit\u00e9 de Montr\u00e9al (1989)."},{"key":"BF02025297_CR13","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1145\/321556.321572","volume":"17","author":"M.A. Breuer","year":"1970","unstructured":"M.A. Breuer, Simplification of the covering problem with application to Boolean expressions, J. ACM 17(1970)166\u2013181.","journal-title":"J. ACM"},{"key":"BF02025297_CR14","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1287\/mnsc.33.3.335","volume":"33","author":"G.G. Brown","year":"1987","unstructured":"G.G. Brown, G.W. Graves and D. Ronen, Scheduling occan transportation of crude oil, Manag. Sci. 33(1987)335\u2013346.","journal-title":"Manag. Sci."},{"key":"BF02025297_CR15","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1093\/comjnl\/14.4.418","volume":"14","author":"N. Christofides","year":"1971","unstructured":"N. Christofides, Zero-one programming using non-binary tree search, Comput. J. 14(1971)418\u2013421.","journal-title":"Comput. J."},{"key":"BF02025297_CR16","volume-title":"A minimax facility location problem and the cardinality constrained set covering problem, MSRR 375","author":"N. Christofides","year":"1975","unstructured":"N. Christofides, A minimax facility location problem and the cardinality constrained set covering problem, MSRR 375, Carnegie-Mellon University, Pittsburgh (1975)."},{"key":"BF02025297_CR17","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1287\/mnsc.21.5.591","volume":"21","author":"N. Christofides","year":"1975","unstructured":"N. Christofides and S. Korman, A computational survey of methods for the set covering problem, Manag. Sci. 21(1975)591\u2013599.","journal-title":"Manag. Sci."},{"key":"BF02025297_CR18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/net.3230110207","volume":"11","author":"N. Christofides","year":"1981","unstructured":"N. Christofides, A. Mingozzi and P. Toth, State space relaxation procedures for the computation of bounds to routing problems, Networks 11(1981)145\u2013164.","journal-title":"Networks"},{"key":"BF02025297_CR19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01942293","volume":"32","author":"R. Church","year":"1974","unstructured":"R. Church and C. Revelle, The maximal covering location problem, Regional Sci. 32(1974)101\u2013118.","journal-title":"Regional Sci."},{"key":"BF02025297_CR20","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal, A greedy heuristic for the set covering problem, Math. Oper. Res. 4(1979)233\u2013235.","journal-title":"Math. Oper. Res."},{"key":"BF02025297_CR21","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1287\/opre.20.5.1010","volume":"20","author":"H.W. Corley","year":"1972","unstructured":"H.W. Corley and S.D. Roberts, A partitioning problem with applications in regional design, Oper. Res. 20(1972)1010\u20131019.","journal-title":"Oper. Res."},{"key":"BF02025297_CR22","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1287\/opre.13.3.482","volume":"13","author":"R.H. Day","year":"1965","unstructured":"R.H. Day, On optimal extracting from a multiple file data storage system: An application of integer programming, Oper. Res. 13(1965)482\u2013494.","journal-title":"Oper. Res."},{"key":"BF02025297_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/trsc.23.1.1","volume":"23","author":"M. Desrochers","year":"1989","unstructured":"M. Desrochers and F. Soumis, A column generation approach to the urban transit crew scheduling, Transp. Sci. 23(1989)1\u201313.","journal-title":"Transp. Sci."},{"key":"BF02025297_CR24","doi-asserted-by":"crossref","unstructured":"J.J. Dongarra, Performance of various computers using standard linear equations software in aFortran environment, Technical Merorandum No. 23, Argonne National Laboratory (1987).","DOI":"10.1177\/003754978704900202"},{"key":"BF02025297_CR25","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01581647","volume":"19","author":"M.E. Dyer","year":"1980","unstructured":"M.E. Dyer, Calculating surrogate constraints, Math. Progr. 19(1980)255\u2013278.","journal-title":"Math. Progr."},{"key":"BF02025297_CR26","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1287\/opre.25.5.760","volume":"25","author":"J. Etcheberry","year":"1977","unstructured":"J. Etcheberry, The set covering problem. A new implicity enumeration algorithm, Oper. Res. 25(1977)760\u2013772.","journal-title":"Oper. Res."},{"key":"BF02025297_CR27","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"T.A. Feo","year":"1989","unstructured":"T.A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Oper. Res. Lett. 8(1989)67\u201371.","journal-title":"Oper. Res. Lett."},{"key":"BF02025297_CR28","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"M.L. Fisher","year":"1989","unstructured":"M.L. Fisher and P. Kedia, Optimal solution of set covering problem\/partitioning problems using dual heuristics, Oper. Res. Lett. 8(1989)67\u201371.","journal-title":"Oper. Res. Lett."},{"key":"BF02025297_CR29","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1002\/1520-6750(198902)36:1<27::AID-NAV3220360103>3.0.CO;2-0","volume":"36","author":"M.L. Fisher","year":"1989","unstructured":"M.L. Fisher and M.B. Rosenwein, An interactive optimisation system for bulk-cargo ship scheduling, Naval Res. Log. 36(1989)27\u201342.","journal-title":"Naval Res. Log."},{"key":"BF02025297_CR30","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1057\/jors.1976.63","volume":"27","author":"B.A. Foster","year":"1976","unstructured":"B.A. Foster and D.M. Ryan, An integer programming approach to the vehicle scheduling problem, Oper. Res. Quarterly 27(1976)367\u2013384.","journal-title":"Oper. Res. Quarterly"},{"key":"BF02025297_CR31","first-page":"361","volume":"18","author":"D.R. Freeman","year":"1967","unstructured":"D.R. Freeman and J.V. Jucker, The line balancing problem, J. Ind. Eng. 18(1967)361\u2013374.","journal-title":"J. Ind. Eng."},{"key":"BF02025297_CR32","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1287\/opre.17.5.848","volume":"17","author":"R.S. Garfinkel","year":"1969","unstructured":"R.S. Garfinkel and G. Nemhauser, The set-partitioning: Set covering with equality constraints, Oper. Res. 17(1969)848\u2013856.","journal-title":"Oper. Res."},{"key":"BF02025297_CR33","doi-asserted-by":"crossref","first-page":"B-495","DOI":"10.1287\/mnsc.16.8.B495","volume":"16","author":"R.S. Garfinkel","year":"1979","unstructured":"R.S. Garfinkel and G.L. Nemhauser, Optimal political districting by implicity enumeration techniques, Manag. Sci. 16(1979)B-495\u2013B-508.","journal-title":"Manag. Sci."},{"key":"BF02025297_CR34","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A.M. Geoffrion","year":"1970","unstructured":"A.M. Geoffrion, Lagrangian relaxation and its use in integer programming, Math. Progr. Study 2(1970)82\u2013114.","journal-title":"Math. Progr. Study"},{"key":"BF02025297_CR35","doi-asserted-by":"crossref","unstructured":"C. Ghiggi, P.P. Puliafito and R. Zoppoli, A combinatorial method for health-care districting, in:Optimization Techniques: Modelling and Optimization in the Service of Man, Part 1, Proc. 7th IFIP Conf. (Springer, 1976).","DOI":"10.1007\/3-540-07622-0_466"},{"key":"BF02025297_CR36","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1109\/PGEC.1965.263993","volume":"EC-14","author":"J.P. Gimpel","year":"1965","unstructured":"J.P. Gimpel, A reduction technique for prime implicant tables, IEEE Trans. Electr. Comp. EC-14(1965)535\u2013541.","journal-title":"IEEE Trans. Electr. Comp."},{"key":"BF02025297_CR37","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/0377-2217(82)90159-X","volume":"10","author":"G. Gunawardane","year":"1982","unstructured":"G. Gunawardane, Dynamic versions of set covering type public facility location problems, Eur. J. Oper. Res. 10(1982)190\u2013195.","journal-title":"Eur. J. Oper. Res."},{"key":"BF02025297_CR38","first-page":"13","volume":"1","author":"E. Heurgon","year":"1982","unstructured":"E. Heurgon, Un probl\u00e8me de recouvrement: l'habillage des horaires d'une ligne d'autobus, RAIRO 1(1982)13\u201329.","journal-title":"RAIRO"},{"key":"BF02025297_CR39","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF01588253","volume":"17","author":"M.H. Karwan","year":"1979","unstructured":"M.H. Karwan and R.L. Rardin, Some relationships between Lagrangian and surrogate duality in integer programming, Math. Progr. 17(1979)320\u2013334.","journal-title":"Math. Progr."},{"key":"BF02025297_CR40","doi-asserted-by":"crossref","first-page":"998","DOI":"10.1287\/opre.19.4.998","volume":"19","author":"C.E. Lemke","year":"1971","unstructured":"C.E. Lemke, H.M. Salkin and K. Spielberg, Set covering by a single-branch enumeration with linear-programming subproblems, Oper. Res. 19(1971)998\u20131022.","journal-title":"Oper. Res."},{"key":"BF02025297_CR41","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/355972.355976","volume":"7","author":"R.E. Marsten","year":"1981","unstructured":"R.E. Marsten, The design of the XMP linear programming library, ACM Trans. Math. Software 7(1981)481\u2013497.","journal-title":"ACM Trans. Math. Software"},{"key":"BF02025297_CR42","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230110208","volume":"11","author":"R. Marsten","year":"1981","unstructured":"R. Marsten and F. Shepardson, Exact solutions of crew scheduling problems using the set partitioning model: Recent successful applications, Networks 11(1981)167\u2013177.","journal-title":"Networks"},{"key":"BF02025297_CR43","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1051\/ro\/1986200402731","volume":"20","author":"M. Minoux","year":"1986","unstructured":"M. Minoux, Optimal traffic assignment in a SS\/TDMA frame: An new approach by set covering and column generation, RAIRO 20(1986)273\u2013286.","journal-title":"RAIRO"},{"key":"BF02025297_CR44","volume-title":"Interactive computer methods for plant layout scheduling and group technology","author":"V. Nakornchai","year":"1982","unstructured":"V. Nakornchai, Interactive computer methods for plant layout scheduling and group technology, Ph.D. Thesis, Department of Management Science, Imperial College, London (1982)."},{"key":"BF02025297_CR45","volume-title":"Algorithms for large scale set covering problems","author":"J.P. Paix\u00e3o","year":"1984","unstructured":"J.P. Paix\u00e3o, Algorithms for large scale set covering problems, Ph.D. Thesis, Department of Management Science, Imperial College, London (1984)."},{"key":"BF02025297_CR46","first-page":"421","volume-title":"Operational Research '90","author":"J.P. Paix\u00e3o","year":"1990","unstructured":"J.P. Paix\u00e3o, Transit crew scheduling on a personal workstation, in:Operational Research '90, ed. H.E. Bradley (Pergamon Press, New York, 1990) pp. 421\u2013432."},{"key":"BF02025297_CR47","unstructured":"M. Parker and B. Smith, Two approaches to computer crew scheduling, in:Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling, ed. A. Wren (North-Holland, 1981) pp. 193\u2013222."},{"key":"BF02025297_CR48","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1111\/j.1538-4632.1976.tb00529.x","volume":"8","author":"C.S. Revelle","year":"1976","unstructured":"C.S. Revelle, C. Toregas and L. Falkson, Applications of the location set covering problem, Geograph. Anal. 8(1976)65\u201376.","journal-title":"Geograph. Anal."},{"key":"BF02025297_CR49","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/0377-2217(89)90389-5","volume":"41","author":"C. Ribeiro","year":"1989","unstructured":"C. Ribeiro, M. Minoux and M.C. Penna, An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment, Eur. J. Oper. Res. 41(1989)232\u2013239.","journal-title":"Eur. J. Oper. Res."},{"key":"BF02025297_CR50","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1287\/trsc.7.1.34","volume":"7","author":"J. Rubin","year":"1973","unstructured":"J. Rubin, A technique for the solution of massive set covering problems with application to airline crew scheduling, Transp. Sci. 7(1973)34\u201338.","journal-title":"Transp. Sci."},{"key":"BF02025297_CR51","first-page":"939","volume":"77","author":"M.E. Salvenson","year":"1955","unstructured":"M.E. Salvenson, The assembly line balancing problem, Trans. ASME 77(1955)939\u2013947.","journal-title":"Trans. ASME"},{"key":"BF02025297_CR52","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/0377-2217(81)90210-1","volume":"6","author":"J.A.M. Schreuder","year":"1981","unstructured":"J.A.M. Schreuder, Application of a location to fire stations in Rotterdam, Eur. J. Oper. Res. 6(1981)212\u2013219.","journal-title":"Eur. J. Oper. Res."},{"key":"BF02025297_CR53","doi-asserted-by":"crossref","first-page":"2274","DOI":"10.1287\/mnsc.26.3.274","volume":"26","author":"F. Shepardson","year":"1980","unstructured":"F. Shepardson and R.E. Marsten, A Lagrangian relaxation algorithm for the two duty period scheduling problem, Manag. Sci. 26(1980)2274\u20132281.","journal-title":"Manag. Sci."},{"key":"BF02025297_CR54","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1137\/1003003","volume":"3","author":"L. Steinberg","year":"1961","unstructured":"L. Steinberg, The background wiring problem: a placement algorithm, SIAM Rev. 3(1961)37.","journal-title":"SIAM Rev."},{"key":"BF02025297_CR55","first-page":"115","volume":"15","author":"F.J. Vasko","year":"1988","unstructured":"F.J. Vasko, F.E. Wolf and K.L. Stott, Optimal selection of ingot sizes via set covering, Oper. Res. 15(1988)115\u2013121.","journal-title":"Oper. Res."},{"key":"BF02025297_CR56","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1287\/opre.35.3.346","volume":"35","author":"F.J. Vasko","year":"1987","unstructured":"F.J. Vasko and F.E. Wolf, Solving large set covering problems on a personal computer, Comp. Oper. Res. 35(1987)346\u2013353.","journal-title":"Comp. Oper. Res."},{"key":"BF02025297_CR57","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1287\/opre.22.2.275","volume":"22","author":"W. Walker","year":"1974","unstructured":"W. Walker, Using the set-covering problem to assign fire companies to fire houses, Oper. Res. 22(1974)275\u2013277.","journal-title":"Oper. Res."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02025297.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02025297\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02025297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T20:08:52Z","timestamp":1586376532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02025297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,5]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,5]]}},"alternative-id":["BF02025297"],"URL":"https:\/\/doi.org\/10.1007\/bf02025297","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,5]]}}}