Migration strategy is key here, please add a section. I'd like to see a single skin change, ahead of time, which can be used to deliver banners from the existing system. Then, we can toggle back and forth between banner providers without the cache purge overhead screwing with the experiment.
It would be good to mention that the design presented here is meant to be trivially migrated to ESI when that is available, cos this is a huge win.
U are using "mincut" in a way that I have not seen before, I assume you mean the allocation mapping's image, and preimage grouped by output element... Please give a definition! Also, the example does not demonstrate how we are compressing the codomain down to the mapping's image—as you explain in the text, there are two normalized tables, one gives criteria bits -> allocation row id, and the second is the banner allocation for that preimage. "mapstring" and "mapline" need more defining also.
I don't get this step: "2. In each map line, check if offset is set"
"name" is not a variation parameter for caching a single banner
"VCL" is the mini-language inside of varnish, so I think you mean "C library called from VCL".