Optimal solutions for multi-unit combinatorial auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics

Full text

Pdf (368 KB)

Source

Electronic Commerce archive
Proceedings of the 2nd ACM conference on Electronic commerce table of contents

Minneapolis, Minnesota, United States

Pages: 13 - 20

Year of Publication: 2000

ISBN:1-58113-272-7

Authors

Rica Gonen	School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel
Daniel Lehmann	School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 24, Citation Count: 21

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/352871.352873 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
	2	M. M. Halldorsson. Approximation of weighted independent set and hereditary subset problems. In Proc. of COCOON'99, number 1627 in Lecture Notes in Computer Science. Springer Verlag, 1999.
	3	J. H~astad. Clique is hard to approximate within Acta Mathematica, 182:105{142, 1999.
	4	R. Holte, August 2000. private communication.
	5	E. Lawler and W. D.E. Branch-and-bound methods: A survey. Operations Research, 14(4):699{719, 1966.
	6	Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
	7	K. Leyton-Brown, Y. Shoham, and M. Tennenholtz. An algorithm for multi-unit combinatorial auctions. Unpublished draft, January 2000.
	8	N. Nisan. Bidding and allocation in combinatorial auctions. Presented at Northwestern's Summer Workshop in Microeconomics, July 1999.
	9	A. H. G. Rinnooy Kan , L. Stougie , C. Vercellis, A class of generalized greedy algorithms for the multi-knapsack problem, Discrete Applied Mathematics, v.42 n.2-3, p.279-290, April 27, 1993 [doi>10.1016/0166-218X(93)90051-O]
	10	M. H. Rothkopf , A. Pekec , R. M. Harstad, Computationally Manageable Combinatorial Auctions, Certer for Discrete Mathematics & Theoretical Computer Science, 1995
	11	Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
	12	M. Tennenholtz. Some tractable combinatorial auctions. Unpublished draft: January 2000.
	13	R. R. Vemuganti. Applications of set covering, set packing and set partitioning models: A survey. In D.-Z. Du and P. M. P., editors, Handbook of Combinatorial Optimization, volume 1, pages 573{746. Kluwer Academic Publishers, 1998.
	14	W. S. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16:8{37, 1961.

CITED BY 21

	Amy Greenwald , Justin Boyan, Bidding algorithms for simultaneous auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.115-124, October 14-17, 2001, Tampa, Florida, USA
	Cuihong Li , Katia Sycara, Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Tuomas Sandholm , Subhash Suri , Andrew Gilpin , David Levine, Winner determination in combinatorial auction generalizations, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Tuomas Sandholm , Subhash Suri, BOB: improved winner determination in combinatorial auctions and generalizations, Artificial Intelligence, v.145 n.1-2, p.33-58, April 2003
	Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA
	Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002
	Athena Vakali , Lefteris Angelis , Dimitra Pournara, Internet based auctions: a survey on models and applications, ACM SIGecom Exchanges, v.2 n.2, p.6-15, Spring, 2001
	Yair Bartal , Rica Gonen , Pierfrancesco La Mura, Negotiation-range mechanisms: exploring the limits of truthful efficient markets, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Vincent Conitzer , Tuomas Sandholm, Expressive negotiation over donations to charities, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	Viet Dung Dang , Nicholas R. Jennings, Optimal clearing algorithms for multi-unit single-item and multi-unit combinatorial auctions with demand/supply function bidding, Proceedings of the 5th international conference on Electronic commerce, p.25-30, September 30-October 03, 2003, Pittsburgh, Pennsylvania
	Riikka-Leena Leskelä , Jeffrey Teich , Hannele Wallenius , Jyrki Wallenius, Decision support for multi-unit combinatorial bundle auctions, Decision Support Systems, v.43 n.2, p.420-434, March, 2007
	Samee Ullah Khan , Ishfaq Ahmad, Comparison and analysis of ten static heuristics-based Internet data replication techniques, Journal of Parallel and Distributed Computing, v.68 n.2, p.113-136, February, 2008
	Amy Greenwald , Justin Boyan, Bidding Algorithms for Simultaneous Auctions: A Case Study, Autonomous Agents and Multi-Agent Systems, v.10 n.1, p.67-89, January 2005
	Eugene Fink , Josh Johnson , Jenny Hu, Exchange Market for Complex Goods: Theory and Experiments, Netnomics, v.6 n.1, p.21-42, April 2004
	Ali Haydar Özer , Can Özturan, A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction, Computers and Operations Research, v.36 n.1, p.196-208, January, 2009
	Shouxi Yang , Alberto Maria Segre , Bruno Codenotti, An optimal multiprocessor combinatorial auction solver, Computers and Operations Research, v.36 n.1, p.149-166, January, 2009
	Eugene Fink , Jianli Gong , Josh Johnson, Exchange market for complex commodities: search for optimal matches, Journal of Experimental & Theoretical Artificial Intelligence, v.19 n.2, p.91-117, June 2007
	Moshe Babaioff , Ron Lavi , Elan Pavlov, Single-value combinatorial auctions and algorithmic implementation in undominated strategies, Journal of the ACM (JACM), v.56 n.1, p.1-32, January 2009
	Kevin Leyton-Brown , Eugene Nudelman , Yoav Shoham, Empirical hardness models: Methodology and a case study on combinatorial auctions, Journal of the ACM (JACM), v.56 n.4, p.1-52, June 2009
	Thomas Sandholm, Making markets and democracy work: a story of incentives and computing, Proceedings of the 18th international joint conference on Artificial intelligence, p.1649-1671, August 09-15, 2003, Acapulco, Mexico