{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:35:24Z","timestamp":1725478524172},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540695134"},{"type":"electronic","value":"9783540695141"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_21","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T05:47:40Z","timestamp":1169617660000},"page":"265-278","source":"Crossref","is-referenced-by-count":0,"title":["An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions"],"prefix":"10.1007","author":[{"given":"J\u00f6rg","family":"Knoche","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Krysta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Andersson, A., Tenhunen, M., Ygge, F.: Integer Programming for Combinatorial Auction Winner Determination. In: Proc.\u00a04th Int. Conf. on Multiagent Systems, ICMAS (2000)","DOI":"10.1109\/ICMAS.2000.858429"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, \u00c9.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Proc. of 14th SODA (2003)","DOI":"10.1080\/15427951.2004.10129086"},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms - ESA \u201997","author":"E.M. Arkin","year":"1997","unstructured":"Arkin, E.M., Hassin, R.: On local search for weighted k-set packing. In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol.\u00a01284. Springer, Heidelberg (1997)"},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(96)00063-7","volume":"71","author":"V. Bafna","year":"1996","unstructured":"Bafna, V., Narayana, B., Ravi, R.: Nonoverlapping local alignments (Weighted independent sets of axis-parallel rectangles). Discr. Applied Math.\u00a071, 41\u201353 (1996)","journal-title":"Discr. Applied Math."},{"issue":"3","key":"21_CR5","first-page":"178","volume":"7","author":"P. Berman","year":"2000","unstructured":"Berman, P.: A d\/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs. Nordic J. Computing\u00a07(3), 178\u2013184 (2000)","journal-title":"Nordic J. Computing"},{"key":"21_CR6","unstructured":"Berman, P., Krysta, P.: Optimizing misdirection. In: Proc. 14th SODA (2003)"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation Techniques for Utilitarian Mechanism Design. In: Proc. 37th ACM STOC (2005)","DOI":"10.1145\/1060590.1060597"},{"key":"21_CR8","unstructured":"Chandra, B., Halld\u00f3rsson, M.M.: Greedy local improvement and weighted packing approximation. In: Proc. SODA (1999)"},{"key":"21_CR9","unstructured":"Fujishima, Y., Leyton-Brown, K., Shoham, Y.: Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In: Proc. 16th Int. Joint Conference on Artificial Intelligence (IJCAI), pp. 548\u2013553 (1999)"},{"key":"21_CR10","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. In: Proc.\u00a039th IEEE FOCS (1998)"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0053959","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M.M. Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson, M.M.: A survey on independent set approximations. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 1\u201314. Springer, Heidelberg (1998)"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-540-45198-3_8","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Hazan","year":"2003","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the Hardness of Approximating k-Dimensional Matching. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 83\u201397. Springer, Heidelberg (2003)"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover, and set packing problems. Discr. Applied Math.\u00a06, 243\u2013254 (1983)","journal-title":"Discr. Applied Math."},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/11549345_53","volume-title":"Mathematical Foundations of Computer Science 2005","author":"P. Krysta","year":"2005","unstructured":"Krysta, P.: Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 615\u2013627. Springer, Heidelberg (2005)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Lehmann, D., O\u2019Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. In: Proc. 1st ACM Conference on Electronic Commerce, EC (1999)","DOI":"10.1145\/336992.337016"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Leyton-Brown, K., Pearson, M., Shoham, Y.: Towards a Universal Test Suite for Combinatorial Auction Algorithms. In: Proc. 2nd ACM Conference on Electronic Commerce, EC (2000)","DOI":"10.1145\/352871.352879"},{"key":"21_CR17","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. In: Proc. 18th AAAI Conf. on Artificial Intelligence (2002)"},{"issue":"2","key":"21_CR18","doi-asserted-by":"publisher","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.\u00a037(2), 130\u2013143 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"21_CR20","unstructured":"Sandholm, T.W.: An algorithm for optimal winner determination in combinatorial auctions. In: Proc. 16th Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 542\u2013547 (1999)"},{"key":"21_CR21","unstructured":"Srinivasan, A.: A extension of the Lov\u00e1sz Local Lemma and its applications to integer programming. In: Proc.\u00a07th ACM-SIAM SODA (1996)"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved Approximation Guarantees for Packing and Covering Integer Programs. SIAM J. Computing\u00a029, 648\u2013670 (1999)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"21_CR23","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1287\/ijoc.15.3.284.16077","volume":"15","author":"S. Vries de","year":"2003","unstructured":"de Vries, S., Vohra, R.: Combinatorial Auctions: A Survey. Informs J. Computing\u00a015(3), 284\u2013309 (2003)","journal-title":"Informs J. Computing"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Zurel, E., Nisan, N.: An Efficient Approximate Allocation Algorithm for Combinatorial Auctions. In: The Proc.\u00a0EC (2001)","DOI":"10.1145\/501158.501172"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T13:56:40Z","timestamp":1683727000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11970125_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}