0
$\begingroup$

Suppose I am solving the generalized assignment problem, so that I am given matrices $U$ and $W$ and a vector $c$ (all three of which have, say, positive entries), and I want to solve $$\text{minimize}_{x_{ij}}\sum_{i,j}u_{ij}x_{ij}s.t.$$ subject to the constraints that $$\sum_{j}w_{ij}x_{ij}\leq c_{i}\text{ for all }i$$ and $$\sum_{i}x_{ij}=1\text{ for all }j$$ with the requirement that $x_{ij}\in\{0,1\}$. This problem is known to be NP-hard. Now, let's suppose that we just happen to get lucky, and there exists a solution $x^{*}$ to the linear programming relaxation of the above integer program that has all entries equal to $0$ or $1$. Is it easy to find this nice solution, given that the solution to the LP relaxation may not be unique?

$\endgroup$
0
$\begingroup$

This is trivial. A solution to the problem is precisely a solution to the linear programming relaxation that happens to have all entries 0 or 1. If there was an easy (i.e. polynomial-time) way to find the "nice solution" when it exists, this would lead to a polynomial-time decision procedure: try the easy way to find the "nice solution", and if unsuccessful conclude that the problem has no solution. If $P \ne NP$, this can't exist.

$\endgroup$

Your Answer

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

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