On LP Relaxations for the Pattern Minimization Problem