I think this is NP-complete, and I don't have the time to think it through.

I have two tables, call them places and people. Both people and places have a location ll. I have a function d( ll a, ll b ) that calculates the distance between locations.

I can create a cartesian join of all possible combination of people and places, thus:

select * from people a, places b

I can refine this into a view that calculates the distance between people and places:

create view distances as
select a.id as aid, a.name as aname, b.id as bid, b.name as bname, d( a.ll, b.ll) as distance

However, I can only assign a person to a place. I know how to find the place closest to a person:

select * from distances
group by bid
having min( distance )

But how do I find the total set of people-> place assignment such that the sum of all assignment distances are minimized, again given that any one person can only be assigned to one place?

I mean I want to select a "slice" of the cartesianed result set, such that people.id is unique in that slice and sum( distance ) for that slice is minimized, but what do I where or group by on?

Thanks.

(Oh, and if anyone wants to post this to askMefi under the heading, "orthogonality isn't a SQL know-it-all after all, let's laugh at him", feel free.)

Ya talked me into it. I seem to have a real weakness for such things.

And let me know if there are tags you want added, and when (and if) the best answer appears.

Thanks hangashore!

"However, I can only assign a person to a place." should be "However, I can only assign a person to one single place.

Also, to give fair warning to potential answerers, the answer has a practical application which is partisan in nature. If you'd prefer not to aid such endeavors, you probably will not wish to help in answering this. I just don't want to take anyone by surprise.

Please assure me that you're not working on behalf of the Alberta Progressive Conservative Party or the Toronto Maple Leafs so that I don't have to burn my keyboard and hack my fingers down to bloody little stumps.

No, not the APCP or the hockey team. And thanks again.