= Solution
For each user define its <set> of eligible ads by
$$
E_i=\{j:\mathcal S^i\cap\mathcal S_j\ne\varnothing\}.
$$
This uses the <intersection> of demographic-group memberships: belonging to one advertised group suffices, because the eligibility condition is a <set union>. A user in several groups still receives at most one ad.
A direct <algorithm> is to process users independently. For user $u_i$, scan ads $a_j$ until finding one for which some group $S_\ell$ belongs to both $\mathcal S^i$ and $\mathcal S_j$. Assign that ad and stop processing this user. If no such ad exists, leave the user unassigned. There is no upper bound on the number of different users who can receive the same ad, so these decisions do not compete for an ad resource.
For correctness, every produced impression has a shared permitted group, and the stopping rule assigns at most one ad to each user. Conversely, a user with $E_i=\varnothing$ cannot receive an ad in any <feasible solution>. Since every other user can contribute at most one impression, every <feasible solution> has value at most
$$
\bigl|\{i:E_i\ne\varnothing\}\bigr|.
$$
The <algorithm> attains this bound, proving
$$
\boxed{\text{maximum impressions}=\bigl|\{i:\mathcal S^i\cap\mathcal S_j\ne\varnothing\text{ for some }j\}\bigr|.}
$$
Represent each membership <set> by a length-$k$ <array> of <Boolean variables>. Testing one user-ad pair costs $O(k)$, so all tests and input setup take $O(nmk+(n+m)k+n+m+k)$ time in <Big O notation>, which is <polynomial time> in all three parameters. For positive $n,m,k$, this simplifies to $O(nmk)$.
A <maximum flow> formulation gives the same result if desired: add <edges> $s\to u_i$ with <flow network edge capacity> $1$, $u_i\to a_j$ with <flow network edge capacity> $1$ exactly when $j\in E_i$, and $a_j\to t$ with <flow network edge capacity> $n$. By the <integral max-flow theorem>, an integral <maximum flow> selects valid impressions. Setting the last <flow network edge capacity> to $1$ would impose an extra restriction absent from this paper.
Back to article page
