{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:39:04Z","timestamp":1760297944337,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540793083"},{"type":"electronic","value":"9783540793090"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-79309-0_28","type":"book-chapter","created":{"date-parts":[[2008,4,19]],"date-time":"2008-04-19T06:31:27Z","timestamp":1208586687000},"page":"315-326","source":"Crossref","is-referenced-by-count":5,"title":["Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems"],"prefix":"10.1007","author":[{"given":"Janina","family":"Brenner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/11758471_19","volume-title":"Algorithms and Complexity","author":"Y. Bleischwitz","year":"2006","unstructured":"Bleischwitz, Y., Monien, B.: Fair cost-sharing methods for scheduling jobs on parallel machines. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol.\u00a03998, pp. 175\u2013186. Springer, Heidelberg (2006)"},{"key":"28_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/978-3-540-70918-3_57","volume-title":"STACS 2007","author":"J. Brenner","year":"2007","unstructured":"Brenner, J., Sch\u00e4fer, G.: Cost sharing methods for makespan and completion time scheduling. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 670\u2013681. Springer, Heidelberg (2007)"},{"key":"28_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03612-9","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"1998","unstructured":"Brucker, P.: Scheduling Algorithms. Springer, New York, USA (1998)"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Chawla, S., Roughgarden, T., Sundararajan, M.: Optimal cost-sharing mechanisms for Steiner forest problems. In: Proc.\u00a0of the 2nd Int.\u00a0Workshop on Internet and Network Economics, pp. 112\u2013123 (2006)","DOI":"10.1007\/11944874_11"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Devanur, N., Mihail, M., Vazirani, V.: Strategyproof cost-sharing mechanisms for set cover and facility location games. In: Proc.\u00a0of the ACM Conference on Electronic Commerce (2003)","DOI":"10.1145\/779928.779942"},{"issue":"3","key":"28_CR6","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0304-3975(90)90100-V","volume":"75","author":"J. Du","year":"1990","unstructured":"Du, J., Leung, J.Y.T., Young, G.H.: Minimizing mean flow time with release time constraint. Theoretical Computer Science\u00a075(3), 347\u2013355 (1990)","journal-title":"Theoretical Computer Science"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0196-6774(03)00078-6","volume":"49","author":"D. Engels","year":"2003","unstructured":"Engels, D., Karger, D., Kolliopoulos, S., Sengupta, S., Uma, R., Wein, J.: Techniques for scheduling with rejection. Journal of Algorithms\u00a049, 175\u2013191 (2003)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"28_CR8","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics\u00a017(2), 416\u2013429 (1969)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"28_CR9","unstructured":"Gupta, A., K\u00f6nemann, J., Leonardi, S., Ravi, R., Sch\u00e4fer, G.: An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. In: Proc.\u00a0of the 18th ACM-SIAM Sympos.\u00a0on Discrete Algorithms, pp. 1153\u20131162 (2007)"},{"key":"28_CR10","unstructured":"Immorlica, N., Mahdian, M., Mirrokni, V.S.: Limitations of cross-monotonic cost sharing schemes. In: Proc.\u00a0of the 16th ACM-SIAM Sympos.\u00a0on Discrete Algorithms, pp. 602\u2013611 (2005)"},{"issue":"4","key":"28_CR11","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T. Kawaguchi","year":"1986","unstructured":"Kawaguchi, T., Kyan, S.: Worst case bound of an LRF schedule for the mean weighted flow time problem. SIAM Journal on Computing\u00a015(4), 1119\u20131129 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR12","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G.: A group-strategyproof mechanism for Steiner forests. In: Proc.\u00a0of the 16th ACM-SIAM Sympos.\u00a0on Discrete Algorithms, pp. 612\u2013619 (2005)"},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1007\/11523468_75","volume-title":"Automata, Languages and Programming","author":"J. K\u00f6nemann","year":"2005","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: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 930\u2013942. Springer, Heidelberg (2005)"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Mehta, A., Roughgarden, T., Sundararajan, M.: Beyond Moulin mechanisms. In: Proc.\u00a0of the ACM Conference on Electronic Commerce (2007)","DOI":"10.1145\/1250910.1250912"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s003550050145","volume":"16","author":"H. Moulin","year":"1999","unstructured":"Moulin, H.: Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice and Welfare\u00a016, 279\u2013320 (1999)","journal-title":"Social Choice and Welfare"},{"key":"28_CR16","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"Phillips, C., Stein, C., Wein, J.: Minimizing average completion time in the presence of release dates. Math. Program\u00a082, 199\u2013223 (1998)","journal-title":"Math. Program"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Sundararajan, M.: New trade-offs in cost-sharing mechanisms. In: Proc.\u00a0of the 38th ACM Sympos.\u00a0on Theory of Computing, pp. 79\u201388 (2006)","DOI":"10.1145\/1132516.1132528"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Sundararajan, M.: Optimal efficiency guarantees for network design mechanisms. In: Proc.\u00a0of the 12th Int.\u00a0Conf.\u00a0on Integer Programming and Combinatorial Optimization, pp. 469\u2013483 (2007)","DOI":"10.1007\/978-3-540-72792-7_35"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"L. Schrage","year":"1968","unstructured":"Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Operations Research\u00a016, 687\u2013690 (1968)","journal-title":"Operations Research"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. Smith","year":"1956","unstructured":"Smith, W.: Various optimizers for single-stage production. Naval Research Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logistics Quarterly"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79309-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T17:50:56Z","timestamp":1657561856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-79309-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540793083","9783540793090"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79309-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}