Network Flow Models for Electronic Barter Exchanges
Can Özturan · Journal of Organizational Computing and Electronic Commerce · 2004
Electronic barter exchange sites are starting to appear on the Internet. In this article, I present three models for direct bartering of items without the use of barter units. The first model allows bartering of items with single instances. The second model barters items with multiple instances. Finally, the third model allows bartering collection of single instance items for other collection of items. In these models, my main objective is to maximize the number of items that are bartered. I also discuss other objectives. I develop a minimum cost network flow based algorithm for the problems described by the first and the second models. I make use of directed hypergraphs and integer programming to solve NP-hard Model 3 problems. I believe that the first model can be suitable for Internet domain name bartering. The second model, on the other hand, can be useful for music or book bartering. Efficient software is readily available for the minimum cost network flow problem and hence can be used for the solution of Model 1 and 2 problems.