The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs):

$$ V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij}, $$

where $\cal P$ is a set of assigned pairs and $w_{ij}$ is an entry of $\bf W$. The indices $i \in \cal A$ and $j \in \cal B$ denote vertices of a bipartite graph.

The fixed $\bf W$ is fine if the disjoint sets remain constant, like the same workers assigned to the same tasks over and over again.

But suppose elements of $\cal A, B$ are parametrized and every $w_{ij}$ of $\bf W$ is actually a function, such as $w(i, j)$. Then the optimal solution depends on the form of this function. Certain functions leave no space for optimization, any assignment would be optimal.

For example.

Weight functions where $V$ is constant and independent of assignment:

  1. $w(i, j) = c_i + c_j$, where $c$ is constant for every $i, j$.

The following weight functions allow optimization by reassignment:

  1. $w(i, j) = c_i \cdot c_j$.
  2. $w(i, j) = XOR(a_i, b_j)$, where $a_i, b_i \in \left\{0, 1\right\}$.
  3. $w(i, j) = \left\| {\bf a}_i - {\bf b}_j\right\|$, that is, $w$ is the Euclidean distance between two two-dimensional vectors of coordinates ${\bf a}_i \in {\cal A}$ and ${\bf b}_j \in {\cal B}$.

Certain functions do not require the Hungarian algorithm and similar for optimal solution. The optimal assignment problem with weights generated by $w(i, j) = XOR(a_i, b_j)$ can be solved by greedy $\arg \max$ over $i$.

Do you know any formal description of the set of functions ${\cal W} \ni w$ for which $V$ is not a constant and optimal assignment is possible? There's something about linear functions that makes them irrelevant to $V$, as in the first example. But I couldn't formalize this idea, and the network optimization literature I've checked treats weights as given constants and does not cover where those constants come from.

Any references to the literature about specific weight functions and solution algorithms sufficient for that functions would be very appreciated as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.