{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T22:09:41Z","timestamp":1762034981537,"version":"build-2065373602"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,2,15]],"date-time":"2021-02-15T00:00:00Z","timestamp":1613347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,15]],"date-time":"2021-02-15T00:00:00Z","timestamp":1613347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16K16005","JP15H06286"],"award-info":[{"award-number":["JP16K16005","JP15H06286"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP24106002","JP25280004"],"award-info":[{"award-number":["JP24106002","JP25280004"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP26280001"],"award-info":[{"award-number":["JP26280001"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009024","name":"Exploratory Research for Advanced Technology","doi-asserted-by":"publisher","award":["JPMJER1201"],"award-info":[{"award-number":["JPMJER1201"]}],"id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K12646"],"award-info":[{"award-number":["JP17K12646"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00453-021-00797-9","type":"journal-article","created":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T19:14:26Z","timestamp":1613675666000},"page":"1653-1676","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Matroid Partitioning Problems"],"prefix":"10.1007","volume":"83","author":[{"given":"Yasushi","family":"Kawase","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0560-5127","authenticated-orcid":false,"given":"Kei","family":"Kimura","sequence":"additional","affiliation":[]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[]},{"given":"Hanna","family":"Sumita","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,15]]},"reference":[{"key":"797_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01193837","volume":"47","author":"L Babel","year":"1998","unstructured":"Babel, L., Kellerer, H., Kotov, V.: The $$k$$-partitioning problem. Math. Methods Oper. Res. 47, 59\u201382 (1998)","journal-title":"Math. Methods Oper. Res."},{"key":"797_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(90)90091-P","volume":"28","author":"RE Burkard","year":"1990","unstructured":"Burkard, R.E., Yao, E.: Constrained partitioning problems. Discret. Appl. Math. 28, 21\u201334 (1990)","journal-title":"Discret. Appl. Math."},{"key":"797_CR3","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1023\/A:1013370208101","volume":"6","author":"SP Chen","year":"2002","unstructured":"Chen, S.P., He, Y., Lin, G.: 3-Partitioning for maximizing the minimum load. J. Comb. Optim. 6, 67\u201380 (2002)","journal-title":"J. Comb. Optim."},{"key":"797_CR4","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/jos.68","volume":"4","author":"M Dell\u2019Amico","year":"2001","unstructured":"Dell\u2019Amico, M., Martello, S.: Bounds for the cardinality constrained $$p, c_{\\max }$$ problem. J. Sched. 4, 123\u2013138 (2001)","journal-title":"J. Sched."},{"key":"797_CR5","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.dam.2005.02.013","volume":"150","author":"P Dell\u2019Olmo","year":"2005","unstructured":"Dell\u2019Olmo, P., Hansen, P., Pallottino, S., Storchi, G.: On uniform $$k$$-partition problems. Discret. Appl. Math. 150, 121\u2013139 (2005)","journal-title":"Discret. Appl. Math."},{"key":"797_CR6","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computer, pp. 624\u2013633. ACM (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"797_CR7","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Minimum partition of a matroid into independent subsets. J. Res. Natl. Bur. Stand. B Math. Math. Phys. 69B, 67\u201372 (1965)","DOI":"10.6028\/jres.069B.004"},{"key":"797_CR8","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and their Applications (Proceedings of the Calgary International Conference on Combinatorial Structures and their Applications 1969), pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"797_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.6028\/jres.069B.016","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J., Fulkerson, D.R.: Transversals and matroid partition. J. Res. Natl. Bur. Stand. 69B, 147\u2013153 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"3","key":"797_CR10","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense $$k$$-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"issue":"4","key":"797_CR11","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/0196-6774(81)90032-8","volume":"2","author":"A Frank","year":"1981","unstructured":"Frank, A.: A weighted matroid intersection algorithm. J. Algorithms 2(4), 328\u2013336 (1981)","journal-title":"J. Algorithms"},{"key":"797_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"797_CR13","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1016\/S0898-1221(03)90201-X","volume":"46","author":"Y He","year":"2003","unstructured":"He, Y., Tan, Z., Zhu, J., Yao, E.: $$k$$-Partitioning problems for maximizing the minimum load. Comput. Math. Appl. 46, 1671\u20131681 (2003)","journal-title":"Comput. Math. Appl."},{"key":"797_CR14","doi-asserted-by":"publisher","unstructured":"Kawase, Y., Kimura, K., Makino, K., Sumita, H.: Optimal matroid partitioning problems. In: Proceedings of the 28th International Symposium on Algorithms and Computer (ISAAC 2017), pp. 51:1\u201351:13 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.51","DOI":"10.4230\/LIPIcs.ISAAC.2017.51"},{"key":"797_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0166-218X(93)90013-E","volume":"45","author":"H Kellerer","year":"1993","unstructured":"Kellerer, H., Woeginger, G.: A tight bound for 3-partitioning. Discret. Appl. Math. 45, 249\u2013259 (1993)","journal-title":"Discret. Appl. Math."},{"key":"797_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21711-5","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2002","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, New York (2002)"},{"key":"797_CR17","unstructured":"Lawler, E.L.: Matroids with parity conditions: a new class of combinatorial optimization problems. Memo. number ERL-M334, Electronic Research Laboratory, College of Engineering, UC Berkeley, Berkeley (1971)"},{"issue":"1","key":"797_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/11083232X","volume":"42","author":"J Lee","year":"2013","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Matroid matching: the power of local search. SIAM J. Comput. 42(1), 357\u2013379 (2013)","journal-title":"SIAM J. Comput."},{"key":"797_CR19","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"797_CR20","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1007\/s11590-013-0637-2","volume":"8","author":"W Li","year":"2014","unstructured":"Li, W., Li, J.: Approximation algorithms for $$k$$-partitioning problems with partition matroid constraint. Optim. Lett. 8, 1093\u20131099 (2014)","journal-title":"Optim. Lett."},{"issue":"2","key":"797_CR21","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L.: Matroid matching and some applications. J. Comb. Theory B 28(2), 208\u2013236 (1980)","journal-title":"J. Comb. Theory B"},{"issue":"7","key":"797_CR22","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4086\/toc.2015.v011a007","volume":"11","author":"D Moshkovitz","year":"2015","unstructured":"Moshkovitz, D.: The projection games conjecture and the NP-hardness of ln $$n$$-approximating set-cover. Theory Comput. 11(7), 221\u2013235 (2015)","journal-title":"Theory Comput."},{"key":"797_CR23","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford University Press, New York (1992)"},{"key":"797_CR24","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, New York (2003)"},{"key":"797_CR25","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10951-013-0359-4","volume":"17","author":"J Verschae","year":"2014","unstructured":"Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. J. Sched. 17, 371\u2013383 (2014)","journal-title":"J. Sched."},{"key":"797_CR26","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2006.11.016","volume":"374","author":"B Wu","year":"2007","unstructured":"Wu, B., Yao, E.: $$k$$-partitioning problems with partition matroid constraint. Theor. Comput. Sci. 374, 41\u201348 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"797_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11766-008-0101-8","volume":"23","author":"B Wu","year":"2008","unstructured":"Wu, B., Yao, E.: Lower bounds and modified LPT algorithm for $$k$$-partitioning problems with partition matroid constraint. Appl. Math. A J. Chin. Univ. 23, 1\u20138 (2008)","journal-title":"Appl. Math. A J. Chin. Univ."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00797-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00797-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00797-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:04:16Z","timestamp":1621937056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00797-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,15]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["797"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00797-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,2,15]]},"assertion":[{"value":"6 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}