News

Colloquia

Direct Bartering

Can Ozturan
Bogazici University
Istanbul, Turkey

Friday, April 21, 2006
MRC 334 A&B - 11:00 a.m. to 12:00 noon
Refreshments at 10:30 a.m.

Abstract:

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.

Hosted by: Joe Flaherty (x-6348)