Car Production
(otherwise known as 15451 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 NPcomplete.
 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