Special matching problem
- From: Michael Hussmann <michael@xxxxxxxxxxxxxxxxxx>
- Date: Thu, 24 Nov 2005 09:05:04 +0100
Hi!
I have a theoretic problem which looks like weighted bipartite matching, but
has another constraint. I have already searched for a solutation but could
not find one.
The problem is as follows: Given n tasks and n processors, each task can run
on any processor but has an affinity a(t,p) \in N to run on a certain
processor.
I want to assign the tasks to the processors, i.e. find a mapping m: t -> p
(1) sum over a(t, m(t)) for all t is maximal
(2) for any two tasks t, t': The affinity a(t, m(t)) is not smaller than the
affinity a(t, m(t')), i.e. to the processor used by t'.
Does there exist a simple solution?
Thanks, Michael
.
- Follow-Ups:
- Re: Special matching problem
- From: Woeginger Gerhard
- Re: Special matching problem
- From: Zig
- Re: Special matching problem
- Prev by Date: Re: Can someone give me an example of this type of problem?
- Next by Date: Re: Special matching problem
- Previous by thread: Proof - the right track?
- Next by thread: Re: Special matching problem
- Index(es):