Re: Special matching problem

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
.

Relevant Pages

  • Re: Special matching problem
    ... Woeginger Gerhard wrote: ... > # I have a theoretic problem which looks like weighted bipartite matching, ...
    (comp.theory)
  • Special matching problem
    ... I have a theoretic problem which looks like weighted bipartite matching, ... has another constraint. ... I have already searched for a solutation but could ... for any two tasks t, t': The affinity a) is not smaller than the ...
    (comp.theory)