{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T04:13:19Z","timestamp":1759032799061},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2016,9,10]],"date-time":"2016-09-10T00:00:00Z","timestamp":1473465600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s10107-016-1068-5","type":"journal-article","created":{"date-parts":[[2016,9,10]],"date-time":"2016-09-10T07:51:48Z","timestamp":1473493908000},"page":"445-469","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Truthful mechanism design via correlated tree rounding"],"prefix":"10.1007","volume":"163","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Idan","family":"Maor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rebecca","family":"Reiffenh\u00e4user","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"key":"1068_CR1","unstructured":"Andelman, N.: Online and strategic aspects of network resource management algorithms. Ph.D. thesis, Tel Aviv University (2006)"},{"issue":"4","key":"1068_CR2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s00224-006-1316-9","volume":"40","author":"N Andelman","year":"2007","unstructured":"Andelman, N., Azar, Y., Sorani, M.: Truthful approximation mechanisms for scheduling selfish related machines. Theory Comput. Syst. 40(4), 423\u2013436 (2007)","journal-title":"Theory Comput. Syst."},{"key":"1068_CR3","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: Proceedings of 42nd Symposium Foundations of Computer Science (FOCS), pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"issue":"2","key":"1068_CR4","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/moor.1110.0534","volume":"37","author":"I Ashlagi","year":"2012","unstructured":"Ashlagi, I., Dobzinski, S., Lavi, R.: Optimal lower bounds for anonymous scheduling mechanisms. Math. Oper. Res. 37(2), 244\u2013258 (2012)","journal-title":"Math. Oper. Res."},{"key":"1068_CR5","doi-asserted-by":"crossref","unstructured":"Azar, Y., Epstein, L., Richter, Y., Woeginger, G.J.: All-norm approximation algorithms. J. Algorithms 52(2),120\u2013133 (2004)","DOI":"10.1016\/j.jalgor.2004.02.003"},{"key":"1068_CR6","volume-title":"Algorithmic Game Theory, chap.\u00a011","author":"L Blumrosen","year":"2007","unstructured":"Blumrosen, L., Nisan, N.: Combinatorial auctions. In: Nisan, N., Tardos, \u00c9., Roughgarden, T., Vazirani, V. (eds.) Algorithmic Game Theory, chap.\u00a011. Cambridge University Press, Cambridge (2007)"},{"key":"1068_CR7","doi-asserted-by":"crossref","unstructured":"Buchfuhrer, D., Dughmi, S., Fu, H., Kleinberg, R., Mossel, E., Papadimitriou, C., Schapira, M., Singer, Y., Umans, C.: Inapproximability for VCG-based combinatorial auctions. In: Proceedings of 21st Symposium Discrete Algorithms (SODA), pp. 518\u2013536 (2010)","DOI":"10.1137\/1.9781611973075.45"},{"issue":"6","key":"1068_CR8","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1137\/080735503","volume":"39","author":"D Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. SIAM J. Comput. 39(6), 2189\u20132211 (2010)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1068_CR9","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1287\/moor.2013.0625","volume":"39","author":"N Chen","year":"2014","unstructured":"Chen, N., Gravin, N., Lu, P.: Truthful generalized assignments via stable matching. Math. Oper. Res. 39(3), 722\u2013736 (2014)","journal-title":"Math. Oper. Res."},{"key":"1068_CR10","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Koutsoupias, E., Kov\u00e1cs, A.: Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms 6(2) (2010)","DOI":"10.1145\/1721837.1721854"},{"issue":"4","key":"1068_CR11","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s00453-008-9165-3","volume":"55","author":"G Christodoulou","year":"2009","unstructured":"Christodoulou, G., Koutsoupias, E., Vidali, A.: A lower bound for scheduling mechanisms. Algorithmica 55(4), 729\u2013740 (2009)","journal-title":"Algorithmica"},{"issue":"4","key":"1068_CR12","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1137\/120866038","volume":"42","author":"G Christodoulou","year":"2013","unstructured":"Christodoulou, G., Kov\u00e1cs, A.: A deterministic truthful PTAS for scheduling related machines. SIAM J. Comput. 42(4), 1572\u20131595 (2013)","journal-title":"SIAM J. Comput."},{"key":"1068_CR13","volume-title":"Combinatorial Auctions","year":"2006","unstructured":"Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)"},{"issue":"3","key":"1068_CR14","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1137\/080744992","volume":"40","author":"P Dhangwatnotai","year":"2011","unstructured":"Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T.: Truthful approximation schemes for single-parameter agents. SIAM J. Comput. 40(3), 915\u2013933 (2011)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1068_CR15","doi-asserted-by":"crossref","first-page":"2287","DOI":"10.1137\/090780146","volume":"42","author":"S Dobzinski","year":"2013","unstructured":"Dobzinski, S., Dughmi, S.: On the power of randomization in algorithmic mechanism design. SIAM J. Comput. 42(6), 2287\u20132304 (2013)","journal-title":"SIAM J. Comput."},{"key":"1068_CR16","unstructured":"Dobzinski, S., Fu, H., Kleinberg, R.: Truthfulness via proxies. CoRR arXiv:1011.3232 (2010)"},{"issue":"4","key":"1068_CR17","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/s00493-011-2528-4","volume":"41","author":"S Dobzinski","year":"2011","unstructured":"Dobzinski, S., Nisan, N.: Limitations of VCG-based mechanisms. Combinatorica 41(4), 379\u2013396 (2011)","journal-title":"Combinatorica"},{"key":"1068_CR18","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: The computational complexity of truthfulness in combinatorial auctions. In: Proceedings of 13th Conference on Electronic Commerce (EC), pp. 405\u2013422 (2012)","DOI":"10.1145\/2229012.2229044"},{"key":"1068_CR19","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: From query complexity to computational complexity. In: Proceedings of 44th Symposium on Theory of Computing (STOC), pp. 1107\u20131116 (2012)","DOI":"10.1145\/2213977.2214076"},{"issue":"1","key":"1068_CR20","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/2786754","volume":"63","author":"S Dobzinski","year":"2016","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: Impossibility results for truthful combinatorial auctions with submodular valuations. J. ACM 63(1), 5 (2016)","journal-title":"J. ACM"},{"key":"1068_CR21","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Ghosh, A.: Truthful assignment without money. In: Proceedings of 11th Conference on Electronic Commerce (EC), pp. 325\u2013334 (2010)","DOI":"10.1145\/1807342.1807394"},{"key":"1068_CR22","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanims: toward optimal combinatorial auctions. In: Proceedings of 43rd Symposium on Theory of Computing (STOC), pp. 149\u2013158 (2011)","DOI":"10.1145\/1993636.1993657"},{"key":"1068_CR23","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1016\/j.geb.2014.01.007","volume":"92","author":"S Dughmi","year":"2015","unstructured":"Dughmi, S., Vondr\u00e1k, J.: Limitations of randomized mechanisms for combinatorial auctions. Games Econom. Behav. 92, 370\u2013400 (2015)","journal-title":"Games Econom. Behav."},{"issue":"1","key":"1068_CR24","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1287\/moor.2015.0730","volume":"41","author":"L Epstein","year":"2016","unstructured":"Epstein, L., Levin, A., van Stee, R.: A unified approach to truthful scheduling on related machines. Math. Oper. Res. 41(1), 332\u2013351 (2016)","journal-title":"Math. Oper. Res."},{"key":"1068_CR25","doi-asserted-by":"crossref","unstructured":"Fadaei, S., Bichler, M.: A truthful-in-expectation mechanism for the generalized assignment problem. In: Proceedings of 10th International Conference on Web and Internet Economics (WINE), pp. 247\u2013248 (2014)","DOI":"10.1007\/978-3-319-13129-0_19"},{"key":"1068_CR26","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: improving the factor of 1-1\/e. In: Proceedings of 47th Symposium on Foundations of Computer Science (FOCS), pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"issue":"3","key":"1068_CR27","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1287\/moor.1110.0499","volume":"36","author":"L Fleischer","year":"2011","unstructured":"Fleischer, L., Goemans, M., Mirrokni, V., Sviridenko, M.: Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36(3), 416\u2013431 (2011)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1068_CR28","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D Hochbaum","year":"1988","unstructured":"Hochbaum, D., Shmoys, D.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1068_CR29","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-007-9105-7","volume":"52","author":"S Khot","year":"2008","unstructured":"Khot, S., Lipton, R., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica 52(1), 3\u201318 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"1068_CR30","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00453-012-9634-6","volume":"66","author":"E Koutsoupias","year":"2013","unstructured":"Koutsoupias, E., Vidali, A.: A lower bound of $$1+\\phi $$ 1 + \u03d5 for truthful scheduling mechanisms. Algorithmica 66(1), 211\u2013223 (2013)","journal-title":"Algorithmica"},{"key":"1068_CR31","doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Proceedings of 13th European Symposium Algorithms (ESA), pp. 616\u2013627 (2005)","DOI":"10.1007\/11561071_55"},{"key":"1068_CR32","doi-asserted-by":"crossref","unstructured":"Krysta, P., V\u00f6cking, B.: Online mechanism design (randomized rounding on the fly). In: Proceedings of 39th International Colloquium Automata, Languages and Programming (ICALP), pp. 636\u2013647 (2012)","DOI":"10.1007\/978-3-642-31585-5_56"},{"issue":"6","key":"1068_CR33","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/2049697.2049699","volume":"58","author":"R Lavi","year":"2011","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. J. ACM 58(6), 25 (2011)","journal-title":"J. ACM"},{"key":"1068_CR34","doi-asserted-by":"crossref","unstructured":"Lehmann, D., O\u2019Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5) (2002)","DOI":"10.1145\/585265.585266"},{"issue":"3","key":"1068_CR35","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J Lenstra","year":"1990","unstructured":"Lenstra, J., Shmoys, D., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Prog. 46(3), 259\u2013271 (1990)","journal-title":"Math. Prog."},{"key":"1068_CR36","doi-asserted-by":"crossref","unstructured":"Lu, P.: On 2-player randomized mechanisms for scheduling. In: Proceedings of 5th International Workshop Internet and Network Economics (WINE), pp. 30\u201341 (2009)","DOI":"10.1007\/978-3-642-10841-9_5"},{"key":"1068_CR37","unstructured":"Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: Proceedings of 25th Symposium on Theoret. Aspects of Computer Science (STACS), pp. 527\u2013538 (2008)"},{"key":"1068_CR38","doi-asserted-by":"crossref","unstructured":"Lu, P., Yu, C.: Randomized truthful mechanisms for scheduling unrelated machines. In: Proceedings of 4th International Workshop Internet and Network Economics (WINE), pp. 402\u2013413 (2008)","DOI":"10.1007\/978-3-540-92185-1_46"},{"key":"1068_CR39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813825","volume-title":"Putting Auction Theory to Work","author":"P Milgrom","year":"2004","unstructured":"Milgrom, P.: Putting Auction Theory to Work. Cambridge University Press, Cambridge (2004)"},{"key":"1068_CR40","doi-asserted-by":"crossref","unstructured":"Mirrokni, V., Schapira, M., Vondr\u00e1k, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proceedings of 9th Conference on Electronic Commerce (EC), pp. 70\u201377 (2008)","DOI":"10.1145\/1386790.1386805"},{"key":"1068_CR41","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econom. Behav. 35, 166\u2013196 (2001)","journal-title":"Algorithmic mechanism design. Games Econom. Behav."},{"issue":"3","key":"1068_CR42","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D Shmoys","year":"1993","unstructured":"Shmoys, D., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Prog. 62(3), 461\u2013474 (1993)","journal-title":"Math. Prog."},{"key":"1068_CR43","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1287\/moor.20.3.583","volume":"20","author":"A Tamir","year":"1995","unstructured":"Tamir, A.: Least majorized elements and generalized polymatroids. Math. Oper. Res. 20, 583\u2013590 (1995)","journal-title":"Math. Oper. Res."},{"key":"1068_CR44","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of 40th Symposium on Theory of Computing (STOC), pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1068-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1068-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1068-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T10:39:57Z","timestamp":1568371197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1068-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,10]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["1068"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1068-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,10]]}}}