{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T19:12:32Z","timestamp":1722885152786},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2003,8]]},"abstract":"<jats:p> To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve dividing a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set [Formula: see text] of n points in the plane into k subsets, [Formula: see text], such that [Formula: see text] is minimized. Variants of this problem arise in applications from the shipbuilding industry. <\/jats:p><jats:p> We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(n log n) and produces a partition that is within a factor (4\/3+\u03b5) of the optimal if k=2, and a factor (2+\u03b5) otherwise. <\/jats:p>","DOI":"10.1142\/s0218195903001190","type":"journal-article","created":{"date-parts":[[2004,1,8]],"date-time":"2004-01-08T09:06:00Z","timestamp":1073552760000},"page":"303-316","source":"Crossref","is-referenced-by-count":3,"title":["BALANCED PARTITION OF MINIMUM SPANNING TREES"],"prefix":"10.1142","volume":"13","author":[{"given":"MATTIAS","family":"ANDERSSON","sequence":"first","affiliation":[{"name":"Department of Computer Science, Lund University, Box 118, 221 00 Lund, Sweden"}]},{"given":"JOACHIM","family":"GUDMUNDSSON","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, TU Eindhoven, Den Dolech 2, P.O. Box 513, 5600 MB Eindhoven , The Netherlands"}]},{"given":"CHRISTOS","family":"LEVCOPOULOS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, Box 118, 221 00 Lund, Sweden"}]},{"given":"GIRI","family":"NARASIMHAN","sequence":"additional","affiliation":[{"name":"School of Computer Science, Florida International University Miami, FL 33199, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322294"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"rf6","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"Garey M. R.","year":"1979"},{"key":"rf7","first-page":"469","volume":"6","author":"Gudmundsson J.","journal-title":"Nordic. Journal of Computing"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0848"},{"key":"rf9","volume-title":"Handbook on Algorithms and Theory of Computation","author":"Karger D.","year":"1998"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50019-X"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195903001190","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:29:14Z","timestamp":1565137754000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195903001190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,8]]}},"alternative-id":["10.1142\/S0218195903001190"],"URL":"https:\/\/doi.org\/10.1142\/s0218195903001190","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}