{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:08Z","timestamp":1725558968602},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_16","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"176-187","source":"Crossref","is-referenced-by-count":8,"title":["Faster Algorithms for Semi-matching Problems (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Jittat","family":"Fakcharoenphol","sequence":"first","affiliation":[]},{"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","unstructured":"Abraham, D.: Algorithmics of two-sided matching problems. Master\u2019s thesis, Department of Computer Science, University of Glasgow (2003)"},{"key":"16_CR2","unstructured":"Bla\u017cewicz, J., Ecker, K., Pesch, E., Schmidt, G., Weglarz, J.: Handbook on scheduling: from theory to applications"},{"key":"16_CR3","unstructured":"Bokal, D., Bresar, B., Jerebic, J.: A generalization of hungarian method and hall\u2019s theorem with applications in wireless sensor networks. arXiv\/0911.1269 (2009)"},{"key":"16_CR4","unstructured":"Bruno, J.L., Coffman Jr., E.G., Sethi, R.: Algorithms for minimizing mean flow time. In: IFIP Congress, pp. 504\u2013510 (1974)"},{"issue":"7","key":"16_CR5","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J.L. Bruno","year":"1974","unstructured":"Bruno, J.L., Coffman Jr., E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. ACM Commun.\u00a017(7), 382\u2013387 (1974)","journal-title":"ACM Commun."},{"key":"16_CR6","first-page":"1277","volume":"11","author":"E.A. Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics Doklady\u00a011, 1277\u20131280 (1970)","journal-title":"Soviet Mathematics Doklady"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/11685654_10","volume-title":"Theoretical Computer Science","author":"Y. Dinitz","year":"2006","unstructured":"Dinitz, Y.: Dinitz\u2019 algorithm: The original version and even\u2019s version. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol.\u00a03895, pp. 218\u2013240. Springer, Heidelberg (2006)"},{"key":"16_CR8","first-page":"93","volume-title":"Combinatorical Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. In: Combinatorical Structures and Their Applications, pp. 93\u201396. Gordon and Breach, New York (1970)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Lekhanukit, B., Nanongkai, D.: Faster algorithms for semi-matching problems. arXiv\/1004.3363 (2010)","DOI":"10.1007\/978-3-642-14165-2_16"},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics\u00a05(2), 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"693","DOI":"10.2197\/ipsjdc.3.693","volume":"3","author":"Y. Harada","year":"2007","unstructured":"Harada, Y., Ono, H., Sadakane, K., Yamashita, M.: Optimal balanced semi-matchings for weighted bipartite graphs. IPSJ Digital Courier\u00a03, 693\u2013702 (2007)","journal-title":"IPSJ Digital Courier"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-92182-0_24","volume-title":"Algorithms and Computation","author":"Y. Harada","year":"2008","unstructured":"Harada, Y., Ono, H., Sadakane, K., Yamashita, M.: The balanced edge cover problem. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 246\u2013257. Springer, Heidelberg (2008)"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Harvey, N.J.A.: Semi-matchings for bipartite graphs and load balancing (slide) (July 2003), http:\/\/people.csail.mit.edu\/nickh\/Publications\/SemiMatching\/Semi-Matching.ppt","DOI":"10.1007\/978-3-540-45078-8_26"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-45078-8_26","volume-title":"Algorithms and Data Structures","author":"N.J.A. Harvey","year":"2003","unstructured":"Harvey, N.J.A., Ladner, R.E., Lov\u00e1sz, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 53\u201378. Springer, Heidelberg (2003)"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Horn, W.A.: Minimizing average flow time with parallel machines. Operations Research, 846\u2013847 (1973)","DOI":"10.1287\/opre.21.3.846"},{"issue":"2","key":"16_CR16","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1006\/jagm.2001.1163","volume":"40","author":"M.-Y. Kao","year":"2001","unstructured":"Kao, M.-Y., Lam, T.W., Sung, W.-K., Ting, H.-F.: An even faster and more unifying algorithm for comparing trees via unbalanced bipartite matchings. J. Algorithms\u00a040(2), 212\u2013233 (2001)","journal-title":"J. Algorithms"},{"key":"16_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11527954_3","volume-title":"Combinatorial and Algorithmic Aspects of Networking","author":"A. Kothari","year":"2005","unstructured":"Kothari, A., Suri, S., T\u00f3th, C.D., Zhou, Y.: Congestion games, load balancing, and price of anarchy. In: L\u00f3pez-Ortiz, A., Hamel, A.M. (eds.) CAAN 2004. LNCS, vol.\u00a03405, pp. 13\u201327. Springer, Heidelberg (2005)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Lee, K., Leung, J.Y.-T., Pinedo, M.L.: Scheduling jobs with equal processing times subject to machine eligibility constraints. Working Paper (2009)","DOI":"10.1007\/s10951-010-0190-0"},{"issue":"12","key":"16_CR19","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1016\/j.ipl.2009.02.010","volume":"109","author":"K. Lee","year":"2009","unstructured":"Lee, K., Leung, J.Y.T., Pinedo, M.L.: A note on an approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Inf. Process. Lett.\u00a0109(12), 608\u2013610 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"16_CR20","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.ijpe.2008.09.003","volume":"116","author":"J.Y.-T. Leung","year":"2008","unstructured":"Leung, J.Y.-T., Li, C.-L.: Scheduling with processing set restrictions: A survey. International Journal of Production Economics\u00a0116(2), 251\u2013262 (2008)","journal-title":"International Journal of Production Economics"},{"issue":"2","key":"16_CR21","doi-asserted-by":"publisher","first-page":"1325","DOI":"10.1016\/j.ejor.2005.03.023","volume":"174","author":"C.-L. Li","year":"2006","unstructured":"Li, C.-L.: Scheduling unit-length jobs with machine eligibility restrictions. European Journal of Operational Research\u00a0174(2), 1325\u20131328 (2006)","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"16_CR22","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0377-2217(02)00914-1","volume":"156","author":"Y. Lin","year":"2004","unstructured":"Lin, Y., Li, W.: Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research\u00a0156(1), 261\u2013266 (2004)","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"16_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1080\/07408170490279598","volume":"36","author":"R. Logendran","year":"2004","unstructured":"Logendran, R., Subur, F.: Unrelated parallel machine scheduling with job splitting. IIE Transactions\u00a036(4), 359\u2013372 (2004)","journal-title":"IIE Transactions"},{"issue":"1","key":"16_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1006\/jctb.1997.1744","volume":"70","author":"L. Lov\u00e1sz","year":"1997","unstructured":"Lov\u00e1sz, L.: The membership problem in jump systems. J. Comb. Theory, Ser. B\u00a070(1), 45\u201366 (1997)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"6","key":"16_CR25","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0020-0190(02)00210-7","volume":"83","author":"C.P. Low","year":"2002","unstructured":"Low, C.P.: An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique. Inf. Process. Lett.\u00a083(6), 315\u2013321 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"16_CR26","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ipl.2006.06.004","volume":"100","author":"C.P. Low","year":"2006","unstructured":"Low, C.P.: An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Inf. Process. Lett.\u00a0100(4), 154\u2013161 (2006) (also appeared in TAMC 2006)","journal-title":"Inf. Process. Lett."},{"issue":"16","key":"16_CR27","doi-asserted-by":"publisher","first-page":"3047","DOI":"10.1016\/j.gaceta.2008.07.003","volume":"52","author":"R. Machado","year":"2008","unstructured":"Machado, R., Tekinay, S.: A survey of game-theoretic approaches in wireless sensor networks. Computer Networks\u00a052(16), 3047\u20133061 (2008)","journal-title":"Computer Networks"},{"key":"16_CR28","unstructured":"Pinedo, M.: Scheduling: Theory, Algorithms, and Systems, 2nd edn. Prentice Hall, Englewood Cliffs (2001)"},{"issue":"3","key":"16_CR29","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s11036-006-5187-8","volume":"11","author":"N. Sadagopan","year":"2006","unstructured":"Sadagopan, N., Singh, M., Krishnamachari, B.: Decentralized utility-based sensor network design. Mob. Netw. Appl.\u00a011(3), 341\u2013350 (2006)","journal-title":"Mob. Netw. Appl."},{"key":"16_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/3-540-45535-3_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"R. Sitters","year":"2001","unstructured":"Sitters, R.: Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 396\u2013405. Springer, Heidelberg (2001)"},{"key":"16_CR31","doi-asserted-by":"crossref","unstructured":"Spyropoulos, C.D., Evans, D.J.: Analysis of the q.a.d. algorithm for an homogeneous multiprocessor computing model with independent memories. International Journal of Computer Mathematics, 237\u2013255","DOI":"10.1080\/00207168508803466"},{"issue":"5","key":"16_CR32","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/s00170-007-1369-1","volume":"40","author":"L.H. Su","year":"2009","unstructured":"Su, L.H.: Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints. The International Journal of Advanced Manufacturing Technology\u00a040(5), 572\u2013581 (2009)","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Suri, S., T\u00f3th, C.D., Zhou, Y.: Uncoordinated load balancing and congestion games in p2p systems. In: IPTPS, pp. 123\u2013130 (2004)","DOI":"10.1007\/978-3-540-30183-7_12"},{"issue":"1","key":"16_CR34","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-006-1211-4","volume":"47","author":"S. Suri","year":"2007","unstructured":"Suri, S., T\u00f3th, C.D., Zhou, Y.: Selfish load balancing and atomic congestion games. Algorithmica\u00a047(1), 79\u201396 (2007) (also appeared in SPAA 2004)","journal-title":"Algorithmica"},{"key":"16_CR35","doi-asserted-by":"crossref","unstructured":"Tamir, A.: Least majorized elements and generalized polymatroids. Mathematics of Operations Research, 583\u2013589 (1995)","DOI":"10.1287\/moor.20.3.583"},{"key":"16_CR36","doi-asserted-by":"crossref","unstructured":"Tamir, T., Vaksendiser, B.: Algorithms for storage allocation based on client preferences. In: International Symposium on Combinatorial Optimization (2008)","DOI":"10.1007\/s10878-009-9259-0"},{"key":"16_CR37","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Data structures and network algorithms. Society for Industrial and Applied Mathematics (1983)","DOI":"10.1137\/1.9781611970265"},{"key":"16_CR38","doi-asserted-by":"crossref","unstructured":"Tomizawa, N.: On some techniques useful for solution of transportation network problems. In: Networks 1, pp. 173\u2013194 (1971)","DOI":"10.1002\/net.3230010206"},{"key":"16_CR39","unstructured":"Vaik, Z.: On scheduling problems with parallel multi-purpose machines. Technical report, Technical Reports, Egervary Research Group on Combinatorial Optimization, Hungary (2005), http:\/\/www.cs.elte.hu\/egres\/tr\/egres-05-02.pdf"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T19:30:26Z","timestamp":1635622226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}