Source code online books for professionals by professionals

Choosing representatives. Ahuja et al. describe this amusing little problem. In a small town, there are n residents, 
x
1
, …, x
n
. There are also m clubs, c
1
, …, c
m
 and k political parties, p
1
, …, p
k
. Each resident is a member of at least one 
club and can belong to exactly one political party. Each club must nominate one of its members to represent it on the 
town council. There is one catch, though: The number of representatives belonging to party p
i
 can be at most u
i
 . It is 
possible to find such a set of representatives? Again, we reduce to maximum flow. As is often the case, we represent 
the objects of the problem as nodes, and the constraints between them as edges and capacities. In this case, we have 
one node per resident, club, and party, as well as the source s and the sink t.
The units of flow represent the representatives. Thus, we give each club an edge from s, with a capacity of 1, 
representing the single person they can nominate. From each club, we add an edge to each of the people belonging to 
that club, as they form the candidates. (The capacities on these edges doesn’t really matter, as long as it’s at least 1.) Note 
that each person can have multiple in-edges (that is, belong to multiple clubs). Now add an edge from the residents to 
their political parties (one each). These edges, once again, have a capacity of 1 (the person is allowed to represent only 
a single club). Finally, add edges from the parties to t so that the edge from party p
i
 has a capacity of u
i
, limiting the 
number of representatives on the council. Finding a maximum flow will now get us a valid set of nominations.
Of course, this max-flow solution gives only a valid set of nominations, not necessarily the one we want. We can 
assume that the party capacities u
i
 are based on democratic principles (some form of vote); shouldn’t the choice of a 
representative similarly be based on the preferences of the club? Maybe they could hold votes to indicate how much 
they’d like each member to represent them, so the members get scores, say, equal to their percentages of the votes. We 
could then try to maximize the sum of these scores, while still ensuring that the nominations are valid, when viewed 
globally. See where I’m going with this? Exactly: We can extend the problem of Ahuja et al. by adding a cost to the 
edges from clubs to residents (equal to 100 – score, for example), and we solve the min-cost max-flow problem. The 
fact that we’re getting a maximum flow will take care of the validity of the nominations, while the cost minimization 
will give us the best compromise, based on club preferences.