All Questions

6
votes
0answers
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 ...
6
votes
0answers
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 $|...