Lower bounds on the finite union probability are established in terms of the individual event probabilities and a weighted sum of the pairwise event probabilities. The lower bounds have at most pseudo-polynomial computational complexity and generalize recent analytical bounds.