Organize a trade event || Business "speed dating" algorithm

Question

I'm Student of software engineering, Right now I am working for my final project, scheduling Business matchmaking on a trade day.

The idea is to bring a seller (developer) and a buyer (A person with financial means) together. The algorithm should be like "Speed Dating".

Let's say I have 15 tables and 10 sessions. It means that each session 15 buyers will meet 15 sellers for 20 minutes.

My question is how do I make the matching?

Suppose each person has 8 attribute that characterize him.
• I thinking creating bipartite graph (group A – Sellers, group B - Buyers)

• Then link up between a seller and buyer based on similar attributes (Should consider what is level of error). dont want to bring together people who are not related

• Then on each session look for a maximum matching.

Constraints: it's not a real time, I'll close registration a few days before the event.

I'm currently "idea blocked" on how to do the linking step (base on a person attributes).

I would appreciate your help, Even a dialogue on the matter would help me a lot!:)

Answer 1

Often given multi-dimensional data that describe data points, you define a similarity or "kernel" between points. This could be the e.g. dot product after you normalize by standard deviation in each dimension for example. Or it could be a Gaussian kernel e^((-d^2)/y) where d is the dot-product between points and y is a constant bandwidth parameter. Also e.g. if certain dimensions are categorical then you could the one-dimensional dot-product to be 1 if the categorical variables agree, otherwise 0. Then you can form the overall dot-product from the multi-dimensional data after normalizing each dimension by its standard deviation. The point is, once you form a similarity or kernel between points, then you can define a weighted bipartite graph where the weight of an edge is equal to the similarity/kernel between points, and your problem is to find a maximum weight matching. This is a well-known problem with solutions in the literature e.g. the Hungarian algorithm, see e.g. http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#In_weighted_bipartite_graphs .