# All Questions

2 questions
76 views
+50

### Solving an LP with at most m-1 nonzeros

Consider the linear program: $$A x = b, ~~~~~~ x\geq 0$$ where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$. It is known that, if this ...
85 views
+50

### Find a minimum-cardinality Hall-violator

Given a bipartite graph $(X,Y，E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set $S \subseteq X$ for which \$|...