The goal is to select a subset of advertisements to serve in a time slot of a specific length to maximize the total value.
The goal is to find a feasible set of winners with a maximum total value.
The problem is NP-hard, but it has efficient constant-factor approximation algorithms as well as an FPTAS.
Therefore, the auction mechanism should incentivize the bidders to reveal their true valuations.
This raises the question: are there truthful mechanisms that work in polynomial time and attain an approximately-optimal outcome?
Mu'alem and Nisan gave the first affirmative answer to this question:[1] they showed that combining two greedy algorithms yields a truthful 2-factor approximation mechanism.
Briest, Krysta and Vocking[2] improved this result by showing a truthful FPTAS.