...

/

Solution: Maximum Advertisement Revenue

Solution: Maximum Advertisement Revenue

Solutions for the Maximum Advertisement Revenue Problem.

Solution 1: Assign the most valuable ad to the most popular place

You wouldn’t be surprised to hear that a greedy strategy maximizes the revenue. Assume that clickspclicks_{p} and priceqprice_{q} are the largest elements: clickspclicks_{p} clicksiclicks_{i} and priceqprice_{q} priceiprice_{i} for all ii = 1,,1,\ldots,nn. We claim that there exists an optimum solution that pairs clickspclicks_{p} with priceqprice_{q}. To prove this, consider an optimum solution and assume that it pairs clickspclicks_{p} with priceqprice_{q} ...