{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T05:12:37Z","timestamp":1651554757201},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,3,18]],"date-time":"2015-03-18T00:00:00Z","timestamp":1426636800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s10479-015-1835-3","type":"journal-article","created":{"date-parts":[[2015,3,17]],"date-time":"2015-03-17T14:21:32Z","timestamp":1426602092000},"page":"565-590","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Valuated matroid-based algorithm for submodular welfare problem"],"prefix":"10.1007","volume":"229","author":[{"given":"Takanori","family":"Maehara","sequence":"first","affiliation":[]},{"given":"Kazuo","family":"Murota","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,3,18]]},"reference":[{"key":"1835_CR1","doi-asserted-by":"crossref","unstructured":"Abrams, Z., Goel, A., & Plotkin, S. (2004). Set $$k$$ k -cover algorithms for energy efficient monitoring in wireless sensor networks. In Proceedings of the 3rd international symposium on information processing in sensor networks (pp. 424\u2013432).","DOI":"10.1145\/984622.984684"},{"key":"1835_CR2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"RK Ahuja","year":"2002","unstructured":"Ahuja, R. K., Ergun, \u00d6., Orlin, J. B., & Punnen, A. P. (2002). A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123, 75\u2013102.","journal-title":"Discrete Applied Mathematics"},{"key":"1835_CR3","doi-asserted-by":"crossref","unstructured":"Andelman, N., & Mansour, Y. (2004). Auctions with budget constraints. In Proceedings of the 9th scandinavian workshop on algorithm theory (SWAT) (pp. 26\u201338).","DOI":"10.1007\/978-3-540-27810-8_4"},{"key":"1835_CR4","doi-asserted-by":"crossref","unstructured":"Azar, Y., Birnbaum, B., & Karlin, A. (2008). Improved approximation algorithms for budgeted allocations. In Automata language and programming (pp. 186\u2013197).","DOI":"10.1007\/978-3-540-70575-8_16"},{"key":"1835_CR5","unstructured":"Beasley, J. E. (1990). ORLIB: Operations research library. http:\/\/people.brunel.ac.uk\/mastjjb\/jeb\/info.html . Accessed November 25, 2013."},{"key":"1835_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0165-4896(98)00015-8","volume":"37","author":"C Bevi\u00e1","year":"1999","unstructured":"Bevi\u00e1, C., Quinzii, M., & Silva, J. A. (1999). Buying several indivisible goods. Mathematical Social Sciences, 37, 1\u201323.","journal-title":"Mathematical Social Sciences"},{"key":"1835_CR7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10479-008-0335-0","volume":"163","author":"Y Chevaleyre","year":"2008","unstructured":"Chevaleyre, Y., Endriss, U., Estivie, S., & Maudet, N. (2008). Multiagent resource allocation in k-additive domains: Preference representation and complexity. Annals of Operations Research, 163, 49\u201362.","journal-title":"Annals of Operations Research"},{"key":"1835_CR8","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0305-0548(96)00032-9","volume":"24","author":"PC Chu","year":"1997","unstructured":"Chu, P. C., & Beasley, J. E. (1997). A genetic algorithm for the generalised assignment problem. Computers and Operations Research, 24, 17\u201323.","journal-title":"Computers and Operations Research"},{"key":"1835_CR9","unstructured":"Conitzer, V., Sandholm, T., & Santi, P. (2005). Combinatorial auctions with k-wise dependent valuations. In Proceedings of the 20th national conference on artificial intelligence (pp. 248\u2013254)."},{"key":"1835_CR10","doi-asserted-by":"crossref","unstructured":"Deshpande, A., & Khuller, S. (2008). Energy efficient monitoring in sensor networks. In LATIN\u2019 08 proceedings of the 8th Latin American conference on theoretical informatics, pp. 436\u2013448.","DOI":"10.1007\/978-3-540-78773-0_38"},{"key":"1835_CR11","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0893-9659(90)90009-Z","volume":"3","author":"AWM Dress","year":"1990","unstructured":"Dress, A. W. M., & Wenzel, W. (1990). Valuated matroid: A new look at the greedy algorithm. Applied Mathematics Letters, 3, 33\u201335.","journal-title":"Applied Mathematics Letters"},{"key":"1835_CR12","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"AWM Dress","year":"1992","unstructured":"Dress, A. W. M., & Wenzel, W. (1992). Valuated matroids. Advances in Mathematics, 93, 214\u2013250.","journal-title":"Advances in Mathematics"},{"key":"1835_CR13","unstructured":"Edmonds, J. (1970). Submodular functions, matroids and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, & J. Sch\u00f6nheim (Eds.), Combinatorial Structures and Their Applications (pp. 69\u201387). New York: Gordon and Breach. Also. In: J\u00fcnger & M., Reinelt, G., & Rinaldi, G. (Eds.) (2003), Combinatorial Optimization-Eureka, You Shrink! (pp. 11\u201326). Berlin: Springer."},{"key":"1835_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978). An analysis of approximations for maximizing submodular set functions-II. Mathematical Programming Study, 8, 73\u201387.","journal-title":"Mathematical Programming Study"},{"key":"1835_CR15","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Goemans, M. X., Mirrokni, V. S., & Sviridenko, M. (2006). Tight approximation algorithms for maximum general assignment problems. In Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithm (pp. 611\u2013620).","DOI":"10.1145\/1109557.1109624"},{"key":"1835_CR16","unstructured":"Frieze, A. M., & Jerrum, M. (1995). Improved approximation algorithms for MAX $$k$$ k -CUT and MAX BISECTION. In Proceedings of the 4th international IPCO conference pp. 1\u201313. Springer: Berlin."},{"key":"1835_CR17","unstructured":"Fujishige, S. (2005). Submodular Functions and Optimization. 2nd ed., Annals of Discrete Mathematics, vol. 58. Amsterdam: Elsevier."},{"key":"1835_CR18","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1287\/moor.28.3.463.16393","volume":"28","author":"S Fujishige","year":"2003","unstructured":"Fujishige, S., & Yang, Z. (2003). A note on Kelso and Crawford\u2019s gross substitutes condition. Mathematics of Operations Research, 28, 463\u2013469.","journal-title":"Mathematics of Operations Research"},{"key":"1835_CR19","unstructured":"Garg, R., Kumar, V., & Pandit, V. (2001). Approximation algorithms for budget-constrained auctions. In APPROX\u201901\/RANDOM\u201901, proceedings of the 4th international workshop on approximation algorithms for combinatorial optimization problems and 5th international workshop on randomization and approximation techniques in computer science: Approximation, random (pp. 102\u2013113)."},{"key":"1835_CR20","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(94)00037-E","volume":"65","author":"F Glover","year":"1996","unstructured":"Glover, F. (1996). Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Applied Mathematics, 65, 223\u2013253.","journal-title":"Discrete Applied Mathematics"},{"key":"1835_CR21","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1006\/jeth.1999.2531","volume":"87","author":"F Gul","year":"1999","unstructured":"Gul, F., & Stacchetti, E. (1999). Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87, 95\u2013124.","journal-title":"Journal of Economic Theory"},{"key":"1835_CR22","doi-asserted-by":"crossref","first-page":"1483","DOI":"10.2307\/1913392","volume":"50","author":"AS Kelso","year":"1982","unstructured":"Kelso, A. S., & Crawford, V. P. (1982). Job matching coalition formation and gross substitutes. Econometrica, 50, 1483\u20131504.","journal-title":"Econometrica"},{"key":"1835_CR23","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D., & Nisan, N. (2006). Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55, 270\u2013296.","journal-title":"Games and Economic Behavior"},{"key":"1835_CR24","doi-asserted-by":"crossref","unstructured":"Liers, F., J\u00fcnger, M., Reinelt, G., & Rinaldi, G. (2004). Computing exact ground states of hard ising spin glass problems by branch-and-cut. In A. Hartmann & H. Rieger (Eds.), New Optimization Algorithms in Physics (pp. 47\u201368). Berlin: Wiley-VCH.","DOI":"10.1002\/3527603794.ch4"},{"key":"1835_CR25","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical programming: The state of the art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L. (1983). Submodular functions and convexity. In A. Bachem, B. Korte, & M. Gr\u00f6tschel (Eds.), Mathematical programming: The state of the art (pp. 235\u2013257). Berlin: Springer."},{"key":"1835_CR26","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/1386790.1386805","volume":"2008","author":"V Mirrokni","year":"2008","unstructured":"Mirrokni, V., Schapira, M., & Vondr\u00e1k, J. (2008). Tight information-theoretic lower bounds for welfare maximization in combinatorial auction. ACM Conference on Electronic Commerce, 2008, 70\u201377.","journal-title":"ACM Conference on Electronic Commerce"},{"key":"1835_CR27","doi-asserted-by":"crossref","unstructured":"Murota, K. (1996a). Valuated matroid intersection, I: Optimality criteria. SIAM Journal on Discrete Mathematics, 9, 545\u2013561.","DOI":"10.1137\/S0895480195279994"},{"key":"1835_CR28","doi-asserted-by":"crossref","unstructured":"Murota, K. (1996b). Valuated matroid intersection, II: Algorithms. SIAM Journal on Discrete Mathematics, 9, 562\u2013576.","DOI":"10.1137\/S0895480195280009"},{"key":"1835_CR29","first-page":"313","volume":"83","author":"K Murota","year":"1998","unstructured":"Murota, K. (1998). Discrete convex analysis. Mathematical Programming, 83, 313\u2013371.","journal-title":"Mathematical Programming"},{"key":"1835_CR30","volume-title":"Matrices and matroids for systems analysis","author":"K Murota","year":"2000","unstructured":"Murota, K. (2000). Matrices and matroids for systems analysis. Berlin: Springer."},{"key":"1835_CR31","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete convex analysis","author":"K Murota","year":"2003","unstructured":"Murota, K. (2003). Discrete convex analysis. Philadelphia: Society for Industrial and Applied Mathematics."},{"key":"1835_CR32","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-3-540-76796-1_11","volume-title":"Research trends in combinatorial optimization","author":"K Murota","year":"2009","unstructured":"Murota, K. (2009). Recent developments in discrete convex analysis. In W. Cook, L. Lov\u00e1sz, & J. Vygen (Eds.), Research trends in combinatorial optimization (pp. 219\u2013260). Berlin: Springer."},{"key":"1835_CR33","first-page":"193","volume":"B23","author":"K Murota","year":"2010","unstructured":"Murota, K. (2010). Submodular function minimization and maximization in discrete convex analysis. RIMS Kokyuroku Bessatsu, B23, 193\u2013211.","journal-title":"RIMS Kokyuroku Bessatsu"},{"key":"1835_CR34","volume-title":"Matroid theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J. G. (1992). Matroid theory. Oxford: Oxford University Press."},{"key":"1835_CR35","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1007\/s13160-012-0082-0","volume":"29","author":"A Shioura","year":"2012","unstructured":"Shioura, A. (2012). Matroid rank functions and discrete concavity. Japan Journal of Industrial and Applied Mathematics, 29, 535\u2013546.","journal-title":"Japan Journal of Industrial and Applied Mathematics"},{"key":"1835_CR36","doi-asserted-by":"crossref","first-page":"92","DOI":"10.15807\/jorsj.55.92","volume":"55","author":"A Shioura","year":"2012","unstructured":"Shioura, A., & Suzuki, S. (2012). Optimal allocation problem with quadratic utility functions and its relationship with graph cut. Journal of Operations Research Society of Japan, 55, 92\u2013105.","journal-title":"Journal of Operations Research Society of Japan"},{"key":"1835_CR37","doi-asserted-by":"crossref","unstructured":"Slijepcevic, S. & Potkonjak, M. (2001). Power efficient organization of wireless sensor networks. In Proceeding of IEEE international conference on communications 2001 (pp. 472\u2013476).","DOI":"10.1109\/ICC.2001.936985"},{"key":"1835_CR38","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/978-3-540-85363-3_20","volume-title":"Approximation, randomization and combinatorial optimization: Algorithms and techniques","author":"A Srinivasan","year":"2008","unstructured":"Srinivasan, A. (2008). Budgeted allocations in the full-information setting. In M. Goemans, K. Jansen, J. D. P. Rolim, & L. Trevisan (Eds.), Approximation, randomization and combinatorial optimization: Algorithms and techniques (pp. 247\u2013253). Berlin: Springer."},{"key":"1835_CR39","unstructured":"Wiegele, A. (2007). Biq Mac Library: A collection of Max-Cut and quadratic 0\u20131 programming instances of medium size. http:\/\/biqmac.uni-klu.ac.at\/biqmaclib ."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-015-1835-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-015-1835-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-015-1835-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T04:41:10Z","timestamp":1651552870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-015-1835-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,18]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["1835"],"URL":"https:\/\/doi.org\/10.1007\/s10479-015-1835-3","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,18]]}}}