Speaker
Dr
Luis Lafuente
(MIT CBA)
Description
Linear Programming can solve some unlikely problems, like
decoding parity check codes, sorting, and other things. A
lovely old theorem by Birkhoff and von Neumann distinguishes
the cases in which the solution is guaranteed to lie on the
integers 0 and 1. Unfortunately, this result fails to apply
to NP-Complete problems -- it guarantees to solve the 8
rooks problem, but not the 8 queens, and also fails to cover
our Sudoku examples. We have explored a number of ways in
which to cast problems as LPs. It seems to matter.
