Ok, creo que las siguientes obras, así que voy a esbozar la idea. Tal vez usted puede comprobar los detalles?
Consideremos el siguiente sistema: Vamos a $C_1, \cdots, C_n$ $n$ columna de sumas. Deje $x_1, \cdots, x_m$ $m$ variables, una para cada fila de una de considerar el siguiente constriants:
\begin{align*}
x_1 + \cdots + x_m &\le \frac{m}2 + \frac{n}2 \ \text{(Type 1)}\\
a_{1i}x_1 + a_{2i}x_2 + \cdots + a_{mi}x_m &\ge \frac{C_i}2, \ 1 \le i \le n \ \text{(Type 2)} \\
x_j &\ge 0, \ 1 \le j \le m \ \text{(Type 3)} \\
x_j &\le 1, \ 1 \le j \le m \ \text{(Type 4)} .
\end{align*}
Tipo $1$ es el relajado versión de decir que no podemos elegir más de $\frac{m+n}2$ filas, y el tipo de $2$ restricciones están diciendo que por cualquier columna, la suma de los valores de las entradas de esa columna (a veces la fila correspondiente de peso) tiene que ser al menos la mitad de la columna "suma". Idealmente, nos gustaría que $x_j \in \{0, 1\}$ pero nos relajamos este.
Ahora observamos que el problema es fácil si $n \ge m.$ Esto es debido a que en este caso, podemos tomar todos de las filas! Por lo tanto, podemos asumir que $m > n$. Si ponemos todas las restricciones en una gran matriz $B$, va a ser $(1 + 2m + n )\times m$. Ahora me reclama que el rango de $B$$m$. De hecho, el tipo de $3$ restricciones sólo nos dan una copia de la $m \times m$ matriz identidad. Por otra parte, el total rango del tipo de $2$ limitaciones se encuentra en la mayoría de las $n$.
Ahora vamos a $x^*$ ser cualquier solución viable para el sistema (por ejemplo, dejar que todo el $x_j = \frac{1}2$). De la discusión anterior, tenemos un $m-n \ge 1$ dimensiones subespacio de $\mathbb{R}^m$ que es ortogonal a todos los de el tipo de $2$ restricciones. Deje $\delta$ ser un vector a partir de que el subespacio. Ahora queremos considerar $x' = x^* + c \delta$ para un adecuado elegido escalares $c$. No conocemos el producto escalar de a $\delta$ con todos los vectores $\mathbf1 \in \mathbb{R}^m$ pero sabemos que $\mathbf 1 \cdot \delta$ es la suma de $e_k \cdot \delta$ para la base de vectores $e_k$. (Estamos considerando $\mathbf 1$ $e_k$ ya que son el tipo de $1$ y escriba $3$ restricciones respectivamente!) Por lo tanto, podemos recoger $c$ tal que $x'$ es una solución para nuestro sistema de arriba y $x_{k} = 0$ o $1$ algunos $k$ (esencialmente $x_{k}$ será el primero en ser ajustado como el que podemos cambiar el valor de $c$ debido a nuestra suposición. Sólo tenemos que elegir el signo de $c$, de modo que el tipo de $1$ restricción no son violados.)
Ahora estamos casi listos. Hay dos casos. Si tenemos $x_k = 1$, entonces podemos quitar el $k$th fila y ajustar la columna de sumas en consecuencia. Además, esto sólo nos ayuda con el tipo de $1$ restricción desde el lado izquierdo del tipo $1$ restricción disminuye por $1$, mientras que el lado derecho sólo disminuye por $\frac{1}2.$ Esto se traducirá en una menor instancia del problema que podemos resolver por inducción.
En el otro caso, seguimos de esta manera haciendo más y más variables igual a $0$. Sin embargo, cada vez que hacemos una variable igual a $0$, debemos elegir un nuevo $\delta$ que es ortogonal a todo el tipo de $2$ restricciones y todo el tipo de $3$ limitaciones que acabamos de hacer apretado. Por lo tanto, podemos hacer algunas $m-n$ de la $x_j's$ igual a $0$ de esta forma. Tenga en cuenta que nosotros no podemos elegir cual de las $x_j's$ $0$ ya que no podemos controlar el producto escalar de a $\mathbf 1 \cdot \delta$. En resumen, tenemos una solución viable $x'$ de que el sistema anterior donde $m-n$ de las variables son iguales a $0$. Ahora sólo tienes que hacer el resto de la $n$ variables igual a $1$. Esto es posible ya que sólo ayuda a todos los de el tipo de $2$ limitaciones ya que todos los coeficientes de $A$ son no-negativos. Además, el tipo de $1$ restricción también está satisfecho ya que
$$x_1 + \cdots + x_m = n < \frac{m}2 + \frac{n}2 $$
donde la desigualdad se sigue de nuestra suposición de que $m > n$ y hemos terminado!
