{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T20:55:20Z","timestamp":1767992120107,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1023\/a:1009802105661","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"7-33","source":"Crossref","is-referenced-by-count":35,"title":["Facility Dispersion Problems Under Capacity and Cost Constraints"],"prefix":"10.1007","volume":"4","author":[{"given":"Daniel J.","family":"Rosenkrantz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giri K.","family":"Tayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.S.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"254803_CR1","doi-asserted-by":"crossref","unstructured":"Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama, \u201cGreedily Finding a Dense Subgraph,\u201d in Proc. Scandinavian Workshop on Algorithm Theory (SWAT'96), Reykjavik, Iceland, July 1996, pp. 136-148.","DOI":"10.1007\/3-540-61422-2_127"},{"key":"254803_CR2","doi-asserted-by":"crossref","unstructured":"C. Baur and S.P. Fekete, \u201cApproximation of Geometric Dispersion Problems,\u201d in Proc. First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'98), Aalborg, Denmark, July 1998, pp. 63-75 (Springer Lecture Notes in Computer Science, vol. 1444).","DOI":"10.1007\/BFb0053964"},{"key":"254803_CR3","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan, \u201cImproved Non-approximability Results,\u201d in Proc. 26th Annual ACM Symposium on Theory of Computing (STOC'94), Montreal, Canada, May 1994, pp. 184-193.","DOI":"10.1145\/195058.195129"},{"key":"254803_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1988","unstructured":"H. Breu and D.G. Kirkpatrick, \u201cUnit disk graph recognition is NP-hard,\u201d Computational Geometry, vol. 9, pp. 3-24, 1988.","journal-title":"Computational Geometry"},{"key":"254803_CR5","doi-asserted-by":"crossref","unstructured":"B. Chandra and M.M. Halld\u00f3rsson, \u201cFacility Dispersion and Remote Subgraphs,\u201d Proc. Scandinavian Workshop on Algorithm Theory (SWAT'96), Reykjavik, Iceland, July 1996.","DOI":"10.1007\/3-540-61422-2_120"},{"issue":"1","key":"254803_CR6","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1287\/moor.6.1.50","volume":"6","author":"R. Chandrasekharan","year":"1981","unstructured":"R. Chandrasekharan and A. Daughety, \u201cLocation on tree networks: p-centre and n-dispersion problems,\u201d Mathematics of Operations Research, vol. 6, no. 1, pp. 50-57, 1981.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"254803_CR7","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1287\/trsc.12.2.107","volume":"12","author":"R.L. Church","year":"1978","unstructured":"R.L. Church and R.S. Garfinkel, \u201cLocating an obnoxious facility on a network,\u201d Transportation Science, vol. 12, no. 2, pp. 107-118, 1978.","journal-title":"Transportation Science"},{"key":"254803_CR8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"B.N. Clark, C.J. Colbourn, and D.S. Johnson, \u201cUnit disk graphs,\u201d Discrete Mathematics, vol. 86, pp. 165-177, 1990.","journal-title":"Discrete Mathematics"},{"key":"254803_CR9","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1991","unstructured":"T. Cormen, C.E. Leiserson, and R. Rivest, Introduction to Algorithms, MIT Press\/McGraw-Hill: Cambridge, MA, 1991."},{"key":"254803_CR10","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0377-2217(89)90420-7","volume":"40","author":"E. Erkut","year":"1989","unstructured":"E. Erkut and S. Neuman, \u201cAnalytical models for locating undesirable facilities,\u201d European Journal of Operational Research, vol. 40, pp. 275-291, 1989.","journal-title":"European Journal of Operational Research"},{"key":"254803_CR11","first-page":"68","volume":"29","author":"E. Erkut","year":"1990","unstructured":"E. Erkut and S. Neuman, \u201cComparison of four models for dispersing facilities,\u201d INFOR, vol. 29, pp. 68-85, 1990.","journal-title":"INFOR"},{"key":"254803_CR12","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/0377-2217(94)00348-3","volume":"92","author":"E. Erkut","year":"1996","unstructured":"E. Erkut, C. ReVelle, and Y. Ulkusal, \u201cInteger-friendly formulations for the r-separation problem,\u201d European Journal of Operational Research, vol. 92, pp. 342-351, 1996.","journal-title":"European Journal of Operational Research"},{"key":"254803_CR13","unstructured":"U. Feige, G. Kortsarz, and D. Peleg, \u201cThe dense k-subgraph problem,\u201d Private communication, April 1999."},{"issue":"2","key":"254803_CR14","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"G.N. Frederickson and D.B. Johnson, \u201cThe complexity of selection and ranking in X +Y and matrices with sorted columns,\u201d Journal of Computer and System Sciences, vol. 24, no. 2, pp. 197-208, 1982.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"254803_CR15","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G.N. Frederickson","year":"1984","unstructured":"G.N. Frederickson and D.B. Johnson, \u201cGeneralized selection and ranking: Sorted matrices,\u201d SIAM Journal on Computing, vol. 13, no. 1, pp. 14-30, 1984.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"254803_CR16","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","volume":"33","author":"Z. Galil","year":"1990","unstructured":"Z. Galil and K. Park, \u201cA linear time algorithm for concave one-dimensional dynamic programming,\u201d Information Processing Letters, vol. 33, no. 6, pp. 309-311, 1990.","journal-title":"Information Processing Letters"},{"issue":"1","key":"254803_CR17","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(92)90135-3","volume":"92","author":"Z. Galil","year":"1992","unstructured":"Z. Galil and K. Park, \u201cDynamic programming with convexity, concavity and sparsity,\u201d Theoretical Computer Science, vol. 92, no. 1, pp. 49-76, 1992.","journal-title":"Theoretical Computer Science"},{"key":"254803_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co.: San Francisco, CA, 1979."},{"issue":"1","key":"254803_CR19","first-page":"B85","volume":"23","author":"A.J. Goldman","year":"1975","unstructured":"A.J. Goldman and P.M. Dearing, \u201cConcepts of optimal locations for partially noxious facilities,\u201d Bulletin of the Operational Research Society of America, vol. 23, no. 1, B85, 1975.","journal-title":"Bulletin of the Operational Research Society of America"},{"key":"254803_CR20","unstructured":"M.M. Halld\u00f3rsson, K. Iwano, N. Katoh, and T. Tokuyama, \u201cFinding Subsets Maximizing Minimum Structures,\u201d in Proc. Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'95), San Francisco, CA, Jan. 1995, pp. 150-157."},{"key":"254803_CR21","unstructured":"P. Hansen and I.D. Moon, \u201cDispersing facilities on a network,\u201d Presentation at the TIMS\/ORSA Joint National Meeting, Washington, DC, 1988."},{"key":"254803_CR22","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/0167-6377(91)90041-M","volume":"10","author":"R. Hassin","year":"1991","unstructured":"R. Hassin and A. Tamir, \u201cImproved complexity bounds for location problems on the real line,\u201d Operations Research Letters, vol. 10, pp. 395-402, 1991.","journal-title":"Operations Research Letters"},{"key":"254803_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0167-6377(97)00034-5","volume":"21","author":"R. Hassin","year":"1997","unstructured":"R. Hassin, S. Rubinstein, and A. Tamir, \u201cApproximation algorithms for maximum dispersion,\u201d Operations Research Letters, vol. 21, pp. 133-137, 1997.","journal-title":"Operations Research Letters"},{"key":"254803_CR24","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, \u201cClique is Hard to Approximate Within n\n1-\u2208,\u201d in Proc. 37th Annual Symposium on Foundations of Computer Science (FOCS'96), Burlington, VT, pp. 627-626, 1996.","DOI":"10.1109\/SFCS.1996.548522"},{"issue":"1","key":"254803_CR25","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"D.S. Hochbaum and W. Maass, \u201cApproximation schemes for covering and packing problems in image processing and VLSI,\u201d J. ACM, vol. 32, no. 1, pp. 130-136, 1985.","journal-title":"J. ACM"},{"issue":"2","key":"254803_CR26","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns, \u201cNC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs,\u201d Journal of Algorithms, vol. 26, no. 2, pp. 238-274, 1998.","journal-title":"Journal of Algorithms"},{"key":"254803_CR27","doi-asserted-by":"crossref","unstructured":"G. Kortsarz and D. Peleg, \u201cOn Choosing a Dense Subgraph,\u201d in Proc. 34th Symposium on Foundations of Computer Science (FOCS'93), Palo Alto, CA, pp. 692-701, 1993.","DOI":"10.1109\/SFCS.1993.366818"},{"key":"254803_CR28","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"M.V. Marathe, H. Breu, H.B. Hunt III, S.S. Ravi, and D.J. Rosenkrantz, \u201cSimple heuristics for unit disk graphs,\u201d Networks, vol. 25, pp. 59-68, 1995.","journal-title":"Networks"},{"key":"254803_CR29","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons: New York, NY, 1990."},{"key":"254803_CR30","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0377-2217(86)90045-7","volume":"24","author":"E. Melachrinoudis","year":"1986","unstructured":"E. Melachrinoudis and T.P. Cullinane, \u201cLocating an undesirable facility with a minimax criterion,\u201d European Journal of Operational Research, vol. 24, pp. 239-246, 1986.","journal-title":"European Journal of Operational Research"},{"key":"254803_CR31","volume-title":"Discrete Location Theory","author":"P.B. Mirchandani","year":"1990","unstructured":"P.B. Mirchandani and R.L. Francis, Discrete Location Theory, John Wiley and Sons, Inc: New York, NY, 1990."},{"issue":"3","key":"254803_CR32","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1287\/mnsc.30.3.290","volume":"30","author":"I.D. Moon","year":"1984","unstructured":"I.D. Moon and S.S. Chaudhry, \u201cAn analysis of network location problems with distance constraints,\u201d Management Science, vol. 30, no. 3, pp. 290-307, 1984.","journal-title":"Management Science"},{"key":"254803_CR33","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"C.H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Co.: Reading, MA, 1994."},{"issue":"3","key":"254803_CR34","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1111\/j.1467-9787.1976.tb00981.x","volume":"16","author":"J. Paroush","year":"1976","unstructured":"J. Paroush and C.S. Tapiero, \u201cOptimal location of a polluting plant on a line under uncertainty,\u201d Journal of Regional Science, vol. 16, no. 3, pp. 365-374, 1976.","journal-title":"Journal of Regional Science"},{"issue":"2","key":"254803_CR35","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"S.S. Ravi","year":"1994","unstructured":"S.S. Ravi, D.J. Rosenkrantz, and G.K. Tayi, \u201cHeuristic and special case algorithms for dispersion problems,\u201d Operations Research, vol. 42, no. 2, pp. 299-310, 1994.","journal-title":"Operations Research"},{"key":"254803_CR36","unstructured":"D.J. Rosenkrantz, G.K. Tayi, and S.S. Ravi, \u201cCapacitated Facility Dispersion Problems,\u201d Technical Report, Department of Computer Science, University at Albany-State University of New York, Aug. 1998."},{"key":"254803_CR37","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0404048","volume":"4","author":"A. Tamir","year":"1991","unstructured":"A. Tamir, \u201cObnoxious facility location on graphs,\u201d SIAM Journal on Discrete Mathematics, vol. 4, pp. 550-567, 1991.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"254803_CR38","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1287\/opre.46.1.157","volume":"46","author":"A. Tamir","year":"1998","unstructured":"A. Tamir, \u201cComments on the paper: 'Heuristic and special case algorithms for dispersion problems' by S.S. Ravi, D.J. Rosenkrantz and G.K. Tayi,\u201d Operations Research, vol. 46, no. 1, pp. 157-158, 1998.","journal-title":"Operations Research"},{"issue":"1","key":"254803_CR39","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0305-0548(91)90040-X","volume":"18","author":"D.J. White","year":"1991","unstructured":"D.J. White, \u201cThe maximal dispersion problem and the 'First point outside the neighborhood' heuristic,\u201d Computers in Operations Research, vol. 18, no. 1, pp. 43-50, 1991.","journal-title":"Computers in Operations Research"},{"issue":"6","key":"254803_CR40","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"D.W. Wong","year":"1988","unstructured":"D.W. Wong and Y.S. Kuo, \u201cA study of two geometric location problems,\u201d Information Processing Letters, vol. 28, no. 6, pp. 281-286, 1988.","journal-title":"Information Processing Letters"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009802105661.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009802105661\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009802105661.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:05:06Z","timestamp":1751281506000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009802105661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["254803"],"URL":"https:\/\/doi.org\/10.1023\/a:1009802105661","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}