{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:39:36Z","timestamp":1787510376997,"version":"build-2736575974"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T00:00:00Z","timestamp":1516579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"AEOLUS"},{"name":"COST 293"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s10479-018-2756-8","type":"journal-article","created":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T04:56:35Z","timestamp":1516596995000},"page":"575-598","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast approximation of matroid packing and covering"],"prefix":"10.1007","volume":"271","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5566-2314","authenticated-orcid":false,"given":"Jerome","family":"Galtier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,1,22]]},"reference":[{"key":"2756_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"A Arora","year":"2012","unstructured":"Arora, A., Hazan, E., & Kale, S. (2012). The multiplicative weights update method: A meta algorithm and applications. Theory of Computing, 8, 121\u2013164.","journal-title":"Theory of Computing"},{"key":"2756_CR2","unstructured":"Baiou, M., & Barahona, F. (2005). A linear programming approach to increasing the weight of all minimum spanning trees. Technical Report Cahier no 2005\u201312, Ecole Polytechnique\u2014Laboratoire d\u2019Econometrie."},{"key":"2756_CR3","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/3828.3829","volume":"32","author":"WH Cunningham","year":"1985","unstructured":"Cunningham, W. H. (1985). Optimal attack and reinforcement of a network. Journal of ACM, 32, 549\u2013561.","journal-title":"Journal of ACM"},{"key":"2756_CR4","doi-asserted-by":"crossref","first-page":"67","DOI":"10.6028\/jres.069B.004","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J. (1965). Minimum partition of a matroid into independent subsets!. Journal of Research of the National Bureau of Standards: B Mathematics and Mathematical Physics, 69B, 67\u201372.","journal-title":"Journal of Research of the National Bureau of Standards: B Mathematics and Mathematical Physics"},{"key":"2756_CR5","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M Fredman","year":"1987","unstructured":"Fredman, M., & Tarjan, R. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34, 596\u2013615.","journal-title":"Journal of the ACM"},{"key":"2756_CR6","volume-title":"Submodular functions and optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S. (2005). Submodular functions and optimization (2nd ed.). New York: Elsevier.","edition":"2"},{"key":"2756_CR7","unstructured":"Galtier, J. (2017). Computing weighted strength and applications to partitioning. (To Appear)."},{"key":"2756_CR8","doi-asserted-by":"crossref","unstructured":"Garg, N., & Konemann, J. (1998). Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th annual symposium on foundations of computer science (pp. 300\u2013309).","DOI":"10.1109\/SFCS.1998.743463"},{"key":"2756_CR9","doi-asserted-by":"crossref","unstructured":"Gilbert, J.\u00a0R. (1987\/1988). Nested dissection is nearly optimal. Information Processing Letters, 26, 325\u2013328.","DOI":"10.1016\/0020-0190(88)90191-3"},{"key":"2756_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10479-012-1200-8","volume":"201","author":"M Grabisch","year":"2012","unstructured":"Grabisch, M., & Skoda, A. (2012). Games induced by the partitioning of a graph. Annals of Operations Research, 201, 229\u2013249.","journal-title":"Annals of Operations Research"},{"key":"2756_CR11","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1112\/jlms\/s1-30.4.494","volume":"1","author":"A Horn","year":"1955","unstructured":"Horn, A. (1955). A characterization of unions of linearly independent sets. Journal of The London Mathematical Society, 1, 494\u2013496.","journal-title":"Journal of The London Mathematical Society"},{"key":"2756_CR12","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D Karger","year":"2000","unstructured":"Karger, D. (2000). Minimum cuts in near-linear time. Journal of the ACM, 47, 46\u201376.","journal-title":"Journal of the ACM"},{"key":"2756_CR13","volume-title":"Combinatorial optimization: Networks and matroids","author":"E Lawler","year":"1976","unstructured":"Lawler, E. (1976). Combinatorial optimization: Networks and matroids. New York: Holt, Rinehart and Winston."},{"key":"2756_CR14","volume-title":"Matrices and matroids for systems analysis","author":"K Murota","year":"2009","unstructured":"Murota, K. (2009). Matrices and matroids for systems analysis. Berlin: Springer."},{"key":"2756_CR15","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C. S. J. A. (1961). Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 36, 445\u2013450.","journal-title":"Journal of the London Mathematical Society"},{"key":"2756_CR16","volume-title":"Matroid theory","author":"J Oxley","year":"1992","unstructured":"Oxley, J. (1992). Matroid theory. Oxford: Oxford University Press."},{"key":"2756_CR17","doi-asserted-by":"crossref","unstructured":"Plotkin, S., Shmoys, D., & Tardos, E. (1991). Fast approximation algorithms for fractional packing and covering problems. In IEEE symposium on foundations of computer science (pp.\u00a0495\u2013504).","DOI":"10.1109\/SFCS.1991.185411"},{"key":"2756_CR18","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A. (1986). Theory of linear and integer programming. New York: Wiley."},{"key":"2756_CR19","volume-title":"Combinatorial optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A. (2003). Combinatorial optimization. Berlin: Springer."},{"key":"2756_CR20","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1002\/net.3230140209","volume":"14","author":"J Suurballe","year":"1984","unstructured":"Suurballe, J., & Tarjan, R. (1984). A quick method for finding shortest pairs of disjoint paths. Networks, 14, 325\u2013336.","journal-title":"Networks"},{"key":"2756_CR21","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.dam.2014.10.023","volume":"213","author":"M Toko-Worou","year":"2016","unstructured":"Toko-Worou, M., & Galtier, J. (2016). Fast approximation for computing the fractional arboricity and extraction of communities of a graph. Discrete Applied Mathematics, 213, 179\u2013195.","journal-title":"Discrete Applied Mathematics"},{"key":"2756_CR22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"36","author":"WT Tutte","year":"1961","unstructured":"Tutte, W. T. (1961). On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society, 36, 221\u2013230.","journal-title":"Journal of the London Mathematical Society"},{"key":"2756_CR23","unstructured":"Young, N. (1995). Randomized rounding without solving the linear program. In Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithm (pp.\u00a0170\u2013178)."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-018-2756-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-2756-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-2756-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,11,23]],"date-time":"2018-11-23T04:43:10Z","timestamp":1542948190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-018-2756-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,22]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["2756"],"URL":"https:\/\/doi.org\/10.1007\/s10479-018-2756-8","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,22]]}}}