{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:06:56Z","timestamp":1736485616607,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343752"},{"type":"electronic","value":"9783540343783"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_19","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T10:34:15Z","timestamp":1149244455000},"page":"175-186","source":"Crossref","is-referenced-by-count":6,"title":["Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines"],"prefix":"10.1007","author":[{"given":"Yvonne","family":"Bleischwitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/S0899-8256(03)00176-3","volume":"47","author":"A. Archer","year":"2004","unstructured":"Archer, A., Feigenbaum, J., Krishnamurthy, A., Sami, R.: Approximation and collusion in multicast cost sharing. Games and Economic Behaviour\u00a047, 36\u201371 (2004)","journal-title":"Games and Economic Behaviour"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, E.: Truthful mechanisms for one-parameter agents. In: Proceedings of the 42th IEEE Symposium on Foundations of Computer Science, pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"19_CR3","unstructured":"Beccetti, L., K\u00f6nemann, J., Leonardi, S., P\u00e1l, M.: Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 375\u2013384 (2005)"},{"key":"19_CR4","unstructured":"Czumaj, A.: Selfish Routing on the Internet. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ch. 42 (2004)"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Devanur, N., Mihail, M., Vazirani, V.: Strategyproof cost sharing mechanisms for set cover and facility location problems. In: Proceedings of ACM Conference on Electronic Commerce, pp. 108\u2013114 (2003)","DOI":"10.1145\/779928.779942"},{"issue":"1-3","key":"19_CR6","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(03)00085-9","volume":"304","author":"J. Feigenbaum","year":"2003","unstructured":"Feigenbaum, J., Krishnamurthy, A., Sami, R., Shenker, S.: Hardness results for multicast cost sharing. Theoretical Computer Science\u00a0304(1-3), 215\u2013236 (2003)","journal-title":"Theoretical Computer Science"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jcss.2001.1754","volume":"63","author":"J. Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Papadimitriou, C., Shenker, S.: Sharing the cost of multicast transmissions. Journal of Computer and System Sciences\u00a063, 21\u201341 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"19_CR8","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/0213013","volume":"13","author":"D. Friesen","year":"1984","unstructured":"Friesen, D.: Tighter bounds for the multifit processor scheduling algorithm. SIAM Journal on Computing\u00a013(1), 170\u2013181 (1984)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"19_CR9","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1137\/0216037","volume":"16","author":"D. Friesen","year":"1987","unstructured":"Friesen, D.: Tighter bounds for lpt scheduling on uniform processors. SIAM Journal on Computing\u00a016(3), 554\u2013560 (1987)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0212004","volume":"12","author":"D. Friesen","year":"1983","unstructured":"Friesen, D., Langston, M.: Bounds for multifit scheduling on uniform processors. SIAM Journal on Computing\u00a012(1), 60\u201370 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/11523468_5","volume-title":"Automata, Languages and Programming","author":"M. Gairing","year":"2005","unstructured":"Gairing, M., L\u00fccking, T., Monien, B., Tiemann, K.: Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 51\u201365. Springer, Heidelberg (2005)"},{"issue":"2","key":"19_CR12","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R. Graham","year":"1969","unstructured":"Graham, R.: Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics\u00a017(2), 416\u2013429 (1969)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"19_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-540-27821-4_13","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., Srinivasan, A., Tardos, E.: Cost-Sharing Mechanisms for Network Design. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 139\u2013150. Springer, Heidelberg (2004)"},{"issue":"1","key":"19_CR14","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. Hochbaum","year":"1987","unstructured":"Hochbaum, D., Shmoys, D.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of the ACM\u00a034(1), 144\u2013162 (1987)","journal-title":"Journal of the ACM"},{"issue":"3","key":"19_CR15","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D. Hochbaum","year":"1988","unstructured":"Hochbaum, D., Shmoys, D.: A polynomial approximation scheme for scheuduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing\u00a017(3), 539\u2013551 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"19_CR16","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. Journal of the Association for Computing Machinery\u00a023(2), 317\u2013327 (1976)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"19_CR17","unstructured":"Immorlica, N., Mahdian, M., Mirrokni, V.: Limitations of cross-monotonic cost sharing schemes. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 602\u2013611 (2005)"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.: Applications of approximate algorithms to cooperative games. In: Proceedings of the 33th Annual ACM Symposium on Theory of Computing, pp. 364\u2013372 (2001)","DOI":"10.1145\/380752.380825"},{"key":"19_CR19","unstructured":"Kent, K., Skorin-Kapov, D.: Population monotonic cost allocation on msts. In: Operational Research Proceedings KOI, pp. 43\u201348 (1996)"},{"key":"19_CR20","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G.: A group-strategyproof mechanism for steiner forests. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 612\u2013619 (2005)"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G., van Zwam, S.: From primal-dual to cost shares and back: a stronger LP relaxation for the steiner forest problem. In: Proceedings of the 32th Int. Colloquium on Automata, Languages, and Programming, pp. 930\u2013942 (2005)","DOI":"10.1007\/11523468_75"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS 1987), pp. 217\u2013224 (1987)","DOI":"10.1109\/SFCS.1987.8"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Sch\u00e4fer, G.: Cross-monotonic cost-sharing methods for connected facility location games. In: ACM Conference on Electronic Commerce, pp. 224\u2013243 (2004)","DOI":"10.1145\/988772.988814"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Mishra, D., Rangarajan, B.: Cost sharing in a job scheduling problem using the shapley value. In: Proceedings of the 6th ACM Conference on Electronic Commerce, pp. 232\u2013239 (2005)","DOI":"10.1145\/1064009.1064034"},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/PL00004200","volume":"18","author":"H. Moulin","year":"2001","unstructured":"Moulin, H., Shenker, S.: Strategyproof sharing of submodular costs: budget balance versus efficiency. Economic Theory\u00a018, 511\u2013533 (2001)","journal-title":"Economic Theory"},{"key":"#cr-split#-19_CR26.1","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic Mechanism Design. Games and Economic Behaviour??35, 166???196 (2001);","DOI":"10.1006\/game.1999.0790"},{"key":"#cr-split#-19_CR26.2","unstructured":"Extended abstract appeard at STOC 1999"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, E.: Group strategyproof mechanisms via primal-dual algorithms. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 584\u2013593 (2003)","DOI":"10.1109\/SFCS.2003.1238231"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Penna, P., Ventre, C.: The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms. In: Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (to appear, 2006)","DOI":"10.1007\/11672142_27"},{"key":"19_CR29","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1002\/nav.3800140404","volume":"14","author":"L.S. Shapley","year":"1967","unstructured":"Shapley, L.S.: On balanced sets and cores. Naval Research Logistics Quarterly\u00a014, 453\u2013460 (1967)","journal-title":"Naval Research Logistics Quarterly"},{"key":"19_CR30","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.orl.2004.05.004","volume":"33","author":"E.V. Shchepin","year":"2005","unstructured":"Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters\u00a033, 127\u2013133 (2005)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:17:21Z","timestamp":1736399841000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11758471_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}