Re: Special matching problem

Woeginger Gerhard wrote:

> Michael Hussmann <michael@xxxxxxxxxxxxxxxxxx> wrote:
> # 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?
>
>
> Define A(t)= max_p a(t,p)
> Define P(t)= {p: a(y,p)=A(t)}
> Define condition (3):
> For any task t: m(t) is an Element of P(t)
>
> Claim: An assignment m satisfies (2) iff it satisfies (3).
> Claim: All assignments that satisfy (3) have the same objective
> values, that is, yield the same sum over a(t,m(t))
>
> Now look for a perfect matching in the bipartite graph between
> tasks and processors, where there is an edge between t and p
> iff p in P(t).
>
> --Gerhard

Hi Gerhard,
that seems to work.
Thank you very much!
Michael
.