Offline Matching Approximation Algorithms in Exchange Markets
Motivated by several marketplace applications on rapidly growing online social networks, we study the problem of effficient o.ine matching algorithms for online exchange markets. We consider two main models of one-shot markets and exchange markets over time. For one-shot markets, we study three main variants of the problem: one-to-one exchange market problem, exchange market problem with short cycles, and probabilistic exchange market problem. We show that all the above problems are NP-hard, and propose heuristics and approximation algorithms for these problems. Experiments show that the number of items exchanged will increase when exchanges through cycles are allowed. Exploring algorithms for markets over time is an interesting direction for future work.
Social Networks Exchange Markets Recommendation Algorithms Set Packing Edge Partitioning
Zeinab Abbassi Laks V. S. Lakshmanan
Department of Computer Science University of British Columbia 2366 Main Mall Vancouver, Canada
国际会议
第十七届国际万维网大会(the 17th International World Wide Web Conference)(WWW08)
北京
英文
2008-04-21（万方平台首次上网日期，不代表论文的发表时间）