Question: Please give the correct algorithm$($Pseudo code format$),$ run$-$time analysis, and proof of correctness. Some Hints: There is a nice direct reduction from this problem to Circulation with Lowerbounds.

The problem states that each user must be shown a single ad$.$ If you did not use reduction to Circulation with Lowerbounds and instead reduced it to the max flow problem, remember to address what happens if the number of users n exceeds the sum of the r$\_$i values for each advertiser i$.($I$.$e$.,$ what if there are more users than the total number of required ads.$)$

The run time of your algorithm must be expressed in terms of the size of the input to the problem, which means you need a polynomial in n$,$ the number of users, m$,$ the number of advertisers, and$/$or k the number of demographic groups. Many gave run times for the original Max Flow problem, in terms of the number of vertices in the flow network. But the flow network is not part of the input of this problem. Instead you build the flow network from the users$/$advertisers$/$groups$,$ which are the inputs to this problem.

Many of you said you were doing a reduction to max flow, but then proceeded to put lowerbounds on the edges. The max flow problem does not have any lower bounds on the edges. Only the circulation problem had an option of lowerbounds on the edges. If you add lowerbounds to some edges, you need to specify lowerbounds on all edges and demand values at all nodes. Then you need to call the Circulation Solver, not the max flow solver. If instead you reduce to max flow, recall that you need the graph you build to have a source node s$,$ a sink node t$,$ and capacities specified for each edge.