Car Production

(otherwise known as 15-451 Extra Credit)

1. 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:

\[\begin{aligned} \sum_{v \in V} y_v &\le k & \\ y_v + y_u &\ge 1 & (u,v) \in E \end{aligned}\]

• 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