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