Min Max-Matching Problem

Question

I have a matching problem and I don't know how to solve it:

Given a complete bipartite graph (A, B).
Each node a_i in A, has two states: s(a_i)=0 or s(a_i)=1
Weighted edges are declared as: w(a_i, b_j, s(a_i))

Fixing a configuration for the states, the problem becomes a max-matching.

The goal is to find the configuration with minimum max-matching.

Example:

|A|=|B|=1
w(a_0, b_0, 0) = 5;
w(a_0, b_0, 1) = 9;

max-matchings are 5 and 9, so 5 is the answer. (so configuration is s(a_0)=0)

Answer 1

I doubt that this is homework, as the questioner is using his real name.

Unfortunately, finding an assignment of states with an approximation ratio better than 2 (assuming Unique Games; 1.3606 otherwise) is NP-hard. Let G be an instance of minimum vertex cover. The set A has a vertex for each edge in G. The set B has a vertex for each vertex in G. Let w(a_j, b_k, 0) be 1 if the lesser endpoint of the edge corresponding to a_j corresponds to b_k, and 0 otherwise. Define w(a_j, b_k, 1) similarly with respect to the greater endpoint. The minimum maximum matching of this instance has cardinality equal to the minimum vertex cover of G, and the latter problem is hard to approximate.

On the algorithms front, we can replace the inner maximum-weight-matching problem by its linear programming dual so as to minimize a minimum. Here y_j is the dual variable corresponding to a_j, and z_k is the dual variable corresponding to b_k.

min ∑_j y_j + ∑_k z_k

s.t.

∀j,k. y_j + z_k ≥ (1 - s(a_j)) w(a_j, b_k, 0) + s(a_j) w(a_j, b_k, 1)

∀j. s(a_j) ∈ {0, 1}

∀j. y_j ≥ 0

∀k. z_k ≥ 0

This formulation is a mixed-integer program, which can be attacked without too much human effort by off-the-shelf software (e.g., the GNU Linear Programming Kit). It may or may not be better than brute force.