Friday, April 21, 2006
MRC 334 A&B - 11:00 a.m. to 12:00 noon
Refreshments at 10:30 a.m.
We present models for direct multi-way bartering of items. By direct, we
mean no barter units
(barter money) are used in transactions and that items are exchanged
directly among barterers whose winning bids form cycles. Bartering can be
useful in grid resource management as well
as e-commerce sites.
We first present a problem called "Used Car salesman Problem". In this
problem, a differential auction-barter market is proposed in which sellers
and buyers can submit bids in the form of a car they will sell or buy and
an additional money amounf (if any) they will request or pay.
Restrictions are also allowed that will enable only one of bids to win. A
polynomial algorithm that employs minimum cost flow formulation will be
presented for solving this problem.
We will also generalize our direct bartering to multiple instance multiple
item versions. These versions are NP-hard. A directed hypergraph model will
be used in order to develop an integer programming formulation of the
problem. Some results from CPLEX solver will be presented.