3
$\begingroup$

For $A = \{a_{ij}\} \in R^{n\times n}$, is finding

$$ \max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i} $$

NP-hard?

$\endgroup$

1 Answer 1

7
$\begingroup$

This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m_1 < \dots < m_\ell$ be the list of edge weights of $G$, let $E_i$ be the set of edges of weight $m_i$, and let $G_i:=G \setminus (E_1 \cup \dots \cup E_i)$. Now test if $G_1$ has a perfect matching (note this can be done in polynomial-time). If no, then the answer is $m_1$. If yes, then test if $G_2$ has a perfect matching and recurse. If $k$ is the first index such that $G_k$ does not have a perfect matching, then output $m_k$ as the answer.

$\endgroup$
2
  • 1
    $\begingroup$ Brilliant idea! Thanks for the answer! $\endgroup$
    – Yuan Gao
    Jan 16, 2015 at 21:52
  • $\begingroup$ If by "recurse" you meant to increment $k$ by $1$, you might instead see better performance in practice by performing a bisection search on $k$. $\endgroup$
    – RobPratt
    Sep 18, 2023 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.