Space Constrained Dynamic Covering
Ioannis Antonellis, Anish Das Sarma, Shaddin Dughmi · 2009
In this paper, we identify a fundamental algorithmic prob-lem that we term space-constrained dynamic covering (SCDC), arising in many modern-day web applications, including ad-serving and online recommendation systems in eBay and Netflix. Roughly speaking, SCDC applies two restrictions to the well-studied Max-Coverage prob-lem [9]: Given an integer k, X = {1, 2,..., n} and I = {S1,..., Sm}, Si ⊆ X, find J ⊆ I, such that |J | ≤ k