This is from a paper by Laszlo Lovasz, can be found here, chapter 4. We have a $(0,1)$-matrix $$A = [a_{ij}]_{i,j=1}^{i=r,j=k}.$$ We then have 2 linear programs:

\begin{align}\min &\quad y\cdot 1\\ \text{s.t.}&\quad yA \geq w\\ &\quad y \geq 0,\end{align}


\begin{align}\max&\quad w\cdot x\\ \text{s.t.}&\quad Ax \leq 1\\ &\quad x \geq 0.\end{align}

Later it is shown that $x = (x_1,\ldots,x_k), w = (w_1,\ldots,w_k)$, which is natural. The bizarre thing is $y = (y_1,\ldots,y_k)$. What is this? I initially thought $yA$ is just a shorthand for $y^TA$, but now I am not sure. I thought that the first LP is the dual of the second LP, but, what?


1 Answer 1


There's a typo in the first occurrence of $y$. It's actually $y=(y_1,\dots,y_r)$ not $y_k$ and this is also used in all further occurrences of $y$ in that paper.

So your initial guess of $yA$ being short for $y^TA$ appears to be correct.

I guess they just omit the transpose sign and always assume matching dimensions. Only the order of the factors in the matrix-vector-product reveals what kind of vector that is.


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.