Consider an assignment problem where we have a set of n stations that can provide service and there is a set of k requests for service. Say, for example, that the stations are cell towers and the requests are cell phones. Each request can be served by a given set of stations. The problem so far can be represented by a bipartite graph G: one side is the stations, the other the customers, and there is an edge (r, y) between customer r and station y if customer x can be served from station y. Assume that each station can serve at most one customer. Using a max-flow computation, we can decide whether or not all customers can be served, or 3 can get an assignment of a subset of customers to stations maximizing the number of served customers Here we consider a version of the problem with an addition complication: Each customer offers a different amount of money for the service. Let U be the set of customers, and assume that customer r U is willing to pay vx 2 0 for being served. Now the goal is to find a subset X C U maximizing 2EX Vz such that there is an assignment of the customers in X to stations Consider the following greedy approach. We process customers in order of decreasing value (breaking ties arbitrarily). When considering customer x the algorithm will either "promise" service to x or reject x in the following greedy fashion. Let X be the set of customers that so far have been promised service. We add r to the set X if and only if there is a way to assign X to servers. and we reject x otherwise. Note that rejected customers will not be considered later. (This is viewed as an advantage: If we need to reject a high- paying customer, at least we can tell him/her early.) However, we do not assign accepting customers to servers in a greedy fashion: we only fix the assignment after the set of accepted customers is fixed. Does this greedy approach produce an optimal set of customers? Prove that it does, or provide a counterexample