1
$\begingroup$

I am working on a variant of the assignment problem. The original assignment problem is as follows:
We are given a bipartite graph with 2n vertices. Each edge has a non-negative integer weight $w_{i,j}$. Missing edges can be handled by giving them very high edge weights. The problem is to find the minimum weight perfect matching. This can be expressed as a linear program:

$\min \sum_{i,j} w_{i,j}x_{i,j}$

such that

$\sum_{i}x_{i,j}=1$

$\sum_{j}x_{i,j}=1$
$x_{ij}\ge0$

This problem can be solved in polynomial time using general purpose linear programming approaches, or even specialized algorithms such as the Hungarian Algorithm.

However, I am interested in finding a perfect matching with a particular weight say W (not minimal). Naively, if we add the constraint $\sum_{i,j}w_{i,j}x_{i,j}\ge W$ to the above linear program, then I don't think we can get integer 0/1 solutions to $x_{i,j}$s since the constraints are no longer totally-unimodular (please correct me if I'm wrong on this).

Another approach I thought of was to encode it as a quadratic program with linear constraints:

$\min \left(\sum_{i,j} w_{i,j}x_{i,j} - W\right)^2$

such that

$\sum_{i}x_{i,j}=1$

$\sum_{j}x_{i,j}=1$
$x_{ij}\ge0$

If $\vec{w}$ is the vector of edge weights, then the squared term can be expressed as
$\vec{x}^{T}\textbf{Q}\vec{x}$, where the matrix $\textbf{Q} = \vec{w}\vec{w}^{T}$, which I believe is positive semidefinite.

My question is, can this quadratic program be solved in polynomial time? Will the optimal $x_{i,j}$s be 0/1 since constraints are totally-unimodular? I am not very familiar with optimization theory so any help will be appreciated.

More generally, is there a way of finding a perfect matching with a particular weight W in polynomial time? Thanks!

$\endgroup$
  • $\begingroup$ What is the application for this? Why would you ever want to do worse than the optimum? $\endgroup$ – saulspatz Feb 17 '18 at 7:53
  • $\begingroup$ @saulspatz I eventually want to enumerate assignments of a particular weight one-by-one. First step is towards that is finding one assignment efficiently. $\endgroup$ – allrtaken Feb 17 '18 at 7:59
  • $\begingroup$ Do you realize that even counting the number of maximal matchings in an unweighted bipartite graph is #P-complete? $\endgroup$ – saulspatz Feb 17 '18 at 8:10
  • $\begingroup$ @saulspatz Yes I know. I don't want to enumerate all - just a few. Murty's algorithm can be used to enumerate the k-best assignments in ascending order of their weight. However, I cannot use that here, as there maybe exponentially many assignments with weights smaller than W. $\endgroup$ – allrtaken Feb 17 '18 at 8:26
  • $\begingroup$ What makes you think that the solution to this QP will be 0-1? $\endgroup$ – Brian Borchers Feb 17 '18 at 15:54

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.