{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:18:25Z","timestamp":1773937105196,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T00:00:00Z","timestamp":1533600000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T00:00:00Z","timestamp":1533600000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR14D2"],"award-info":[{"award-number":["JPMJCR14D2"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-018-0493-7","type":"journal-article","created":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T13:16:39Z","timestamp":1533647799000},"page":"188-211","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Envy-Free Matchings with Lower Quotas"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7316-5434","authenticated-orcid":false,"given":"Yu","family":"Yokoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,7]]},"reference":[{"key":"493_CR1","first-page":"1","volume":"80","author":"A Arulselvan","year":"2016","unstructured":"Arulselvan, A., Cseh, \u00c1., Gro\u00df, M., Manlove, D.F., Matuschke, J.: Matchings with lower quotas: algorithms and complexity. Algorithmica 80, 1\u201324 (2016)","journal-title":"Algorithmica"},{"key":"493_CR2","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT, Electronic Colloquium on Computational Complexity Report (2003)"},{"key":"493_CR3","doi-asserted-by":"publisher","first-page":"3136","DOI":"10.1016\/j.tcs.2010.05.005","volume":"411","author":"P Bir\u00f3","year":"2010","unstructured":"Bir\u00f3, P., Fleiner, T., Irving, R.W., Manlove, D.F.: The college admissions problem with lower and common quotas. Theor. Comput. Sci. 411, 3136\u20133153 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"493_CR4","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.jet.2014.03.004","volume":"153","author":"L Ehlers","year":"2014","unstructured":"Ehlers, L., Hafalir, I.E., Yenmez, M.B., Yildirim, M.A.: School choice with controlled choice constraints: hard bounds versus soft bounds. J. Econ. Theory 153, 648\u2013683 (2014)","journal-title":"J. Econ. Theory"},{"key":"493_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-45535-3_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"Tam\u00e1s Fleiner","year":"2001","unstructured":"Fleiner, T.: A matroid generalization of the stable matching polytope. In: Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2001), Lecture Notes in Computer Science 2081, pp. 105\u2013114. Springer, Berlin (2001)"},{"key":"493_CR6","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1287\/moor.28.1.103.14256","volume":"28","author":"T Fleiner","year":"2003","unstructured":"Fleiner, T.: A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 28, 103\u2013126 (2003)","journal-title":"Math. Oper. Res."},{"key":"493_CR7","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1287\/moor.2015.0751","volume":"41","author":"T Fleiner","year":"2016","unstructured":"Fleiner, T., Kamiyama, N.: A matroid approach to stable matchings with lower quotas. Math. Oper. Res. 41, 734\u2013744 (2016)","journal-title":"Math. Oper. Res."},{"key":"493_CR8","first-page":"6:1","volume":"4","author":"D Fragiadakis","year":"2015","unstructured":"Fragiadakis, D., Iwasaki, A., Troyan, P., Ueda, S., Yokoo, M.: Strategyproof matching with minimum quotas. ACM Trans. Econ. Comput. 4, 6:1\u20136:40 (2015)","journal-title":"ACM Trans. Econ. Comput."},{"key":"493_CR9","doi-asserted-by":"crossref","unstructured":"Frank, A.: Generalized polymatroids, Finite and Infinite Sets. In: Proceedings of the 6th Hungarian Combinatorial Colloquium, 1981, Colloquia Mathematica Societatis J\u00e1nos Bolyai, 37, 285\u2013294. North-Holland (1984)","DOI":"10.1016\/B978-0-444-86893-0.50021-8"},{"key":"493_CR10","series-title":"Oxford Lecture Series in Mathematics and its Applications","volume-title":"Connections in Combinatorial Optimization","author":"A Frank","year":"2011","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and its Applications, vol. 38. Oxford University Press, Oxford (2011)"},{"key":"493_CR11","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A Frank","year":"1988","unstructured":"Frank, A., Tardos, \u00c9.: Generalized polymatroids and submodular flows. Math. Prog. 42, 489\u2013563 (1988)","journal-title":"Math. Prog."},{"key":"493_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0377-2217(83)90078-4","volume":"13","author":"AM Frieze","year":"1983","unstructured":"Frieze, A.M.: Complexity of a 3-dimensional assignment problem. Eur. J. Oper. Res. 13, 161\u2013164 (1983)","journal-title":"Eur. J. Oper. Res."},{"key":"493_CR13","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"493_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","volume":"11","author":"D Gale","year":"1985","unstructured":"Gale, D., Sotomayor, M.: Some remarks on the stable matching problem. Discret. Appl. Math. 11, 223\u2013232 (1985)","journal-title":"Discret. Appl. Math."},{"key":"493_CR15","unstructured":"Garey, M.\u00a0R., Johnson, D.\u00a0S.:\u00a029: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman. San Francisco (1979)"},{"key":"493_CR16","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2016.02.002","volume":"235","author":"M Goto","year":"2016","unstructured":"Goto, M., Iwasaki, A., Kawasaki, Y., Kurata, R., Yasuda, Y., Yokoo, M.: Strategyproof matching with regional minimum and maximum quotas. Artif. Intell. 235, 40\u201357 (2016)","journal-title":"Artif. Intell."},{"key":"493_CR17","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)"},{"key":"493_CR18","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-23719-5_16","volume-title":"Algorithms \u2013 ESA 2011","author":"Koki Hamada","year":"2011","unstructured":"Hamada, K., Iwama, K., Miyazaki, S.: The hospitals, residents problem with quota lower bounds. In: Proceedings of 19th Annual European Symposium on Algorithms (ESA 2011), Lecture Notes in Computer Science, vol. 6942, pp. 180\u2013191. Springer, Berlin (2011)"},{"key":"493_CR19","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/s00453-014-9951-z","volume":"74","author":"K Hamada","year":"2016","unstructured":"Hamada, K., Iwama, K., Miyazaki, S.: The hospitals\/residents problem with lower quotas. Algorithmica 74, 440\u2013465 (2016)","journal-title":"Algorithmica"},{"key":"493_CR20","unstructured":"Hassin, R.: On Network Flows, Ph.D. Thesis, Yale University (1978)"},{"key":"493_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/net.3230120102","volume":"12","author":"R Hassin","year":"1982","unstructured":"Hassin, R.: Minimum cost flow with set-constraints. Networks 12, 1\u201321 (1982)","journal-title":"Networks"},{"key":"493_CR22","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1257\/0002828054825466","volume":"95","author":"JW Hatfield","year":"2005","unstructured":"Hatfield, J.W., Milgrom, P.R.: Matching with contracts. Am. Econ. Rev. 95, 913\u2013935 (2005)","journal-title":"Am. Econ. Rev."},{"key":"493_CR23","doi-asserted-by":"crossref","unstructured":"Huang, C.C.: Classified stable matching. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2010), pp. 1235\u20131253. SIAM, Philadelphia (2010)","DOI":"10.1137\/1.9781611973075.99"},{"key":"493_CR24","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1257\/aer.20101552","volume":"105","author":"Y Kamada","year":"2014","unstructured":"Kamada, Y., Kojima, F.: Efficient matching under distributional constraints: theory and applications. Am. Econ. Rev. 105, 67\u201399 (2014)","journal-title":"Am. Econ. Rev."},{"key":"493_CR25","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.jet.2016.12.006","volume":"168","author":"Y Kamada","year":"2017","unstructured":"Kamada, Y., Kojima, F.: Stability concepts in matching under distributional constraints. J. Econ. Theory 168, 107\u2013142 (2017)","journal-title":"J. Econ. Theory"},{"key":"493_CR26","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific Publishing, Singapore (2013)"},{"key":"493_CR27","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-319-66700-3_25","volume-title":"Algorithmic Game Theory","author":"Matthias Mnich","year":"2017","unstructured":"Mnich, M., Schlotter, I.: Stable marriage with covering constraints\u2013a complete computational trichotomy. In: Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT 2017), pp. 320\u2013332. Springer, Berlin (2017)"},{"key":"493_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)"},{"key":"493_CR29","first-page":"151","volume":"1","author":"K Murota","year":"2016","unstructured":"Murota, K.: Discrete convex analysis: A tool for economics and game theory. J. Mech. Inst. Des. 1, 151\u2013273 (2016)","journal-title":"J. Mech. Inst. Des."},{"key":"493_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1287\/moor.24.1.95","volume":"24","author":"K Murota","year":"1999","unstructured":"Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95\u2013105 (1999)","journal-title":"Math. Oper. Res."},{"key":"493_CR31","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"JB Orlin","year":"1993","unstructured":"Orlin, J.B.: A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41, 338\u2013350 (1993)","journal-title":"Oper. Res."},{"key":"493_CR32","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92, 991\u20131016 (1984)","journal-title":"J. Polit. Econ."},{"key":"493_CR33","doi-asserted-by":"publisher","first-page":"47","DOI":"10.2307\/1911460","volume":"52","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: Stability and polarization of interests in job matching. Econometrica 52, 47\u201357 (1984)","journal-title":"Econometrica"},{"key":"493_CR34","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2307\/1913160","volume":"54","author":"AE Roth","year":"1986","unstructured":"Roth, A.E.: On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica 54, 425\u2013427 (1986)","journal-title":"Econometrica"},{"key":"493_CR35","volume-title":"Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis","author":"A\u00a0E Roth","year":"1992","unstructured":"Roth, A\u00a0.E., Sotomayor, M\u00a0.A\u00a0.O.: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, Cambridge (1992)"},{"key":"493_CR36","first-page":"359","volume-title":"Matroid Theory","author":"\u00c9 Tardos","year":"1985","unstructured":"Tardos, \u00c9.: Generalized matroids and supermodular colourings. In: Lov\u00e1sz, L., Recski, A. (eds.) Matroid Theory, pp. 359\u2013382. Amsterdam, North-Holland (1985)"},{"key":"493_CR37","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9 Tardos","year":"1985","unstructured":"Tardos, \u00c9.: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 247\u2013255 (1985)","journal-title":"Combinatorica"},{"key":"493_CR38","unstructured":"Wu, Q., Roth, A.E.: The lattice of envy-free matchings. Mimeo (2016)"},{"key":"493_CR39","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1287\/moor.2016.0802","volume":"42","author":"Y Yokoi","year":"2017","unstructured":"Yokoi, Y.: A generalized polymatroid approach to stable matchings with lower quotas. Math. Oper. Res. 42, 238\u2013255 (2017)","journal-title":"Math. Oper. Res."},{"key":"493_CR40","unstructured":"Yokoi, Y.: Envy-free matchings with lower quotas. In: Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), pp. 67:1\u201367:12 (2017)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0493-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0493-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0493-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:37:01Z","timestamp":1589697421000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0493-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,7]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["493"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0493-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,7]]},"assertion":[{"value":"29 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}