Car Production
(otherwise known as 15-451 Extra Credit)
- Binary LPs. Binary Linear Programming is like linear programming, with the additional constraint that all variables must take on values either 0 or 1. The decision version of binary linear programming asks whether or not there exists a point satisfying all the constraints.
Show that BinLP is NP-complete.
- Roses are red, carnations are another
-
We’ll first reduce from vertex cover
- Let the problem be \(k, (V, E)\)
-
Then make \(y_v\) for \(v\) in \(V\)
- Now consider the constraints below
- That gives us one more thing to show:
- An edge \((u,v)\) sum’s satisfied, when
-
\(y_v = 1\) or \(y_u = 1\), then
- These correspond to \(v\) or \(u\)
-
Being chosen, or maybe both, too
- So once we’ve solved this problem we’re done
-
\(v\)’s in the cover when \(y_v\)’s 1
- The first constraint now saves the day
-
It bounds the cover by at most \(k\)
- Next’s to prove we’re in NP
-
But that part’s pretty clear to me
- Just take the given solution set,
-
Add’em up, they’ll work, I bet
- So BinLP’s both hard and in NP
- Therefore, QED