{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:26Z","timestamp":1740109406735,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,9,17]],"date-time":"2016-09-17T00:00:00Z","timestamp":1474070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s00224-016-9704-2","type":"journal-article","created":{"date-parts":[[2016,9,17]],"date-time":"2016-09-17T01:04:27Z","timestamp":1474074267000},"page":"641-663","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design"],"prefix":"10.1007","volume":"59","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4020-4334","authenticated-orcid":false,"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahimeh","family":"Ramezani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,17]]},"reference":[{"issue":"6","key":"9704_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing 8(6), 121\u2013164 (2012)","journal-title":"Theory of Computing"},{"issue":"4","key":"9704_CR2","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/S0097539705447293","volume":"35","author":"D Bienstock","year":"2006","unstructured":"Bienstock, D., Iyengar, G.: Approximating fractional packings and coverings in O(1\/epsilon) iterations. SIAM J. Comput. 35(4), 825\u2013854 (2006)","journal-title":"SIAM J. Comput."},{"key":"9704_CR3","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. In: STOC, pp. 39\u201348 (2005)","DOI":"10.1145\/1060590.1060597"},{"key":"9704_CR4","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Elbassioni, K., Fouz, M.: Truthful mechanisms for exhibitions. In: WINE, pp. 170\u2013181 (2010)","DOI":"10.1007\/978-3-642-17572-5_14"},{"issue":"3","key":"9704_CR5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/rsa.10033","volume":"20","author":"RD Carr","year":"2002","unstructured":"Carr, R.D., Vempala, S.: Randomized metarounding. Random Struct. Algoritm. 20(3), 343\u2013352 (2002)","journal-title":"Random Struct. Algoritm."},{"key":"9704_CR6","unstructured":"Dughmi, S., Roughgarden, T., Vondr\u00e1k, J., Yan, Q.: An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries. arXiv: 1109.1053 (2011)"},{"key":"9704_CR7","unstructured":"Elbassioni, K., Jha, M.: On the power of combinatorial bidding in web display ads. In: ICIW, pp. 46\u201355 (2015)"},{"key":"9704_CR8","doi-asserted-by":"crossref","unstructured":"Elbassioni, K., Mehlhorn, K., Ramezani, F.: Towards more practical linear programming-based techniques for algorithmic mechanism design. In: Hoefer, M. (ed.) Algorithmic Game Theory, Volume 9347 of Lecture Notes in Computer Science, pp. 98\u2013109. Springer, Berlin, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48433-3_8"},{"issue":"2","key":"9704_CR9","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0167-6377(95)00032-0","volume":"18","author":"MD Grigoriadis","year":"1995","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: A sublinear-time randomized approximation algorithm for matrix games. Oper. Res. Lett. 18(2), 53\u201358 (1995)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9704_CR10","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1137\/S0097539704446232","volume":"37","author":"N Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630\u2013652 (2007). a preliminary version appeared in FOCS 1998","journal-title":"SIAM J. Comput."},{"key":"9704_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"key":"9704_CR12","doi-asserted-by":"crossref","unstructured":"Hoefer, M., Kesselheim, T., V\u00f6cking, B.: Approximation algorithms for secondary spectrum auctions. In: SPAA, pp. 177\u2013186 (2011)","DOI":"10.1145\/1989493.1989520"},{"key":"9704_CR13","unstructured":"K\u00f6nemann, J.: Fast Combinatorial Algorithms for Packing and Covering Problems. Master\u2019s Thesis, Fachbereich Informatik, Universit\u00e4t des Saarlandes (1997)"},{"key":"9704_CR14","doi-asserted-by":"crossref","unstructured":"Kraft, D., Fadaei, S., Bichler, M.: Fast convex decomposition for truthful social welfare approximation. In: WINE, pp. 120\u2013132 (2014)","DOI":"10.1007\/978-3-319-13129-0_9"},{"key":"9704_CR15","unstructured":"Khandekar, R.: Lagrangian Relaxation Based Algorithms for Convex Programming Problems. PhD Thesis, Indian Institute of Technology, Delhi, India (2004)"},{"key":"9704_CR16","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S., Stein, C.: Approximating disjoint-path problems using greedy algorithms and packing integer programs. In: IPCO, pp. 153\u2013168 (1998)","DOI":"10.1007\/3-540-69346-7_12"},{"key":"9704_CR17","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: FOCS, pp. 494\u2013504 (2007)","DOI":"10.1109\/FOCS.2007.62"},{"key":"9704_CR18","doi-asserted-by":"crossref","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: FOCS, pp. 595\u2013604 (2005)","DOI":"10.1109\/SFCS.2005.76"},{"issue":"6","key":"9704_CR19","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":"9704_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511800481"},{"key":"9704_CR21","doi-asserted-by":"crossref","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. In: FOCS, pp. 495\u2013504 (1991)","DOI":"10.1109\/SFCS.1991.185411"},{"issue":"2","key":"9704_CR22","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37(2), 130\u2013143 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9704_CR23","unstructured":"Wang, D., Rao, S., Mahoney, M.W.: Unified acceleration method for packing and covering problems via diameter reduction. arXiv: 1508.02439 (2015)"},{"key":"9704_CR24","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: FOCS, pp. 538\u2013546 (2001)","DOI":"10.1109\/SFCS.2001.959930"},{"key":"9704_CR25","unstructured":"Zhu, Z.A., Orecchia, L.: Nearly-linear time positive LP solver with faster convergence rate. In: STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 229\u2013236 (2015)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9704-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9704-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9704-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T19:01:57Z","timestamp":1498330917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9704-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,17]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["9704"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9704-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,9,17]]}}}