  Effective bounds on the union probability are well known to be beneficial in
the analysis of stochastic problems in many areas, including probability
theory, information theory, statistical communications, computing and
operations research. In this work we present new results on bounding the
probability of a finite union of events, ${P\left(\bigcup_{i=1}^N A_i\right)}$,
for a fixed positive integer ${N}$, using partial information on the events in
terms of ${\{P(A_i)\}}$ and ${\{\sum_j c_j P(A_i\cap A_j)\}}$ where ${c_1}$,
${\dots}$, ${c_N}$ are given weights. We derive two new classes of lower bounds
of at most pseudo-polynomial computational complexity. These classes of lower
bounds generalize the existing bound in \cite{Kuai2000} and recent bounds in
\cite{Yang2014,Yang2014ISIT} and are numerically shown to be tighter in some
cases than the Gallot-Kounias bound \cite{Gallot1966,Kounias1968} and the
Pr{\'e}kopa-Gao bound \cite{Prekopa2005} which require more information on the
events probabilities.
