{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:52Z","timestamp":1725559012090},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_30","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"349-361","source":"Crossref","is-referenced-by-count":14,"title":["A ( $2 - c\\frac{{\\rm log} N}{N}$ )\u2013Approximation Algorithm for the Stable Marriage Problem"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuya","family":"Okamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0304-0208(08)73101-3","volume-title":"Analysis and Design of Algorithms for Combinatorial Problems, Annals of Disc. Math.","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. In: Analysis and Design of Algorithms for Combinatorial Problems, Annals of Disc. Math., vol.\u00a025, pp. 27\u201346. Elsevier Science Publishing Company, Amsterdam (1985)"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"Algorithms and Data Structures","author":"P. Berman","year":"1995","unstructured":"Berman, P., Fujito, T.: On the approximation properties of independent set problem in degree 3 graphs. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 449\u2013460. Springer, Heidelberg (1995)"},{"key":"30_CR3","unstructured":"Elde, T.: Assignment engine. Senior Honours Project Report, Department of Computing Science, University of Glasgow (2000)"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D. Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Amer. Math. Monthly\u00a069, 9\u201315 (1962)","journal-title":"Amer. Math. Monthly"},{"key":"30_CR5","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. Discrete Applied Mathematics\u00a011, 223\u2013232 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR6","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D. Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston (1989)"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0304-3975(03)00321-9","volume":"306","author":"M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M., Irving, R., Iwama, K., Manlove, D., Miyazaki, S., Morita, Y., Scott, S.: Approximability results for stable marriage problems with ties. Theoretical Computer Science\u00a0306, 431\u2013447 (2003)","journal-title":"Theoretical Computer Science"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/3-540-45071-8_35","volume-title":"Computing and Combinatorics","author":"M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Randomized approximation of the stable marriage problem. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 339\u2013350. Springer, Heidelberg (2003)"},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-540-39658-1_26","volume-title":"Algorithms - ESA 2003","author":"M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation of the stable marriage problem. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 266\u2013277. Springer, Heidelberg (2003)"},{"key":"30_CR10","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In: Proc. SODA 2000, pp. 329\u2013337 (2000)"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"R. Irving","year":"1994","unstructured":"Irving, R.: Stable marriage and indifference. Discrete Applied Mathematics\u00a048, 261\u2013272 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/3-540-68530-8_32","volume-title":"Algorithms - ESA \u201998","author":"R. Irving","year":"1998","unstructured":"Irving, R.: Matching medical students to pairs of hospitals: a new variation on an old theme. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 381\u2013392. Springer, Heidelberg (1998)"},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-44985-X_24","volume-title":"Algorithm Theory - SWAT 2000","author":"R. Irving","year":"2000","unstructured":"Irving, R., Manlove, D., Scott, S.: The hospitals\/Residents problem with ties. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 259\u2013271. Springer, Heidelberg (2000)"},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/3-540-48523-6_41","volume-title":"Automata, Languages and Programming","author":"K. Iwama","year":"1999","unstructured":"Iwama, K., Manlove, D., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 443\u2013452. Springer, Heidelberg (1999)"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M.: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. In: Rolim, J.D.P. (ed.) RANDOM 1997. LNCS, vol.\u00a01269, pp. 1\u201314. Springer, Heidelberg (1997) ,A (2 \u2212 c N )\u2013Approximation Algorithm for the Stable Marriage Problem 361"},{"key":"30_CR16","unstructured":"Le, T., Bhushan, V., Amin, C.: First aid for the match, 2nd edn. McGraw-Hill, Medical Publishing Division (2001)"},{"issue":"1-2","key":"30_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"D. Manlove","year":"2002","unstructured":"Manlove, D., Irving, R., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoretical Computer Science\u00a0276(1-2), 261\u2013279 (2002)","journal-title":"Theoretical Computer Science"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf.\u00a022, 115\u2013123 (1985)","journal-title":"Acta Inf."},{"key":"30_CR19","first-page":"3251","volume":"E86-A","author":"H. Nagamochi","year":"2003","unstructured":"Nagamochi, H., Nishida, Y., Ibaraki, T.: Approximability of the minimum maximal matching problem in planar graphs. Institute of Electronics, Information and Communication Engineering, Transactions on Fundamentals\u00a0E86-A, 3251\u20133258 (2003)","journal-title":"Institute of Electronics, Information and Communication Engineering, Transactions on Fundamentals"},{"key":"30_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/3-540-48777-8_32","volume-title":"Integer Programming and Combinatorial Optimization","author":"C.P. Teo","year":"1999","unstructured":"Teo, C.P., Sethuraman, J.V., Tan, W.P.: Gale-shapley stable marriage problem revisited: Strategic issues and applications. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 429\u2013438. Springer, Heidelberg (1999)"},{"key":"30_CR21","unstructured":"Zito, M.: Randomized techniques in combinatorial algorithmics. PhD thesis, Dept. of Computer Science, University of Warwick (1999)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:27:10Z","timestamp":1620012430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}