论文标题
Maxspace广告问题的近似算法
Approximation algorithms for the MAXSPACE advertisement problem
论文作者
论文摘要
$ \ newcommand {\ cala} {\ Mathcal {a}} $在Maxspace中，给定一组ADS $ \ CALA $，一个人希望安排一个子集$ {\ cala'\ cala'\ subseteq \ cala} $ in $ k $ k $ k $ k $ k $ s $ {每个广告$ {a_i \ in \ cala} $都有尺寸$ s_i $和频率$ w_i $。如果任何插槽中的广告总数最多为$ l $，并且每个广告{a_i \ in \ cala'} $出现在$ w_i $插槽中，而每个插槽中最多一次。目标是找到一个可行的时间表，以最大程度地提高所有插槽所占用的空间之和。我们考虑了一个称为MaxSpace-R的概括，AD $ a_i $也有发布日期$ r_i $，并且如果$ {j \ ge r_i} $，则只能出现在插槽$ b_j $中。对于此变体，我们提供了$ 1/9 $ - APPRXIMATION算法。此外，我们考虑MaxSpace-rdv的AD $ A_I $还具有截止日期$ d_i $（并且只能出现在带有$ r_i \ l le j \ le j \ le d_i $的插槽$ b_j $中，并且值$ v_i $，这是每个分配的副本$ a_i $的副本（可能是$ a_i $ be $ s_i $）。当$ k $由常数界定时，我们为此问题提供了一个多项式时间近似方案。这是人们可以期望的最好的因素，因为Maxspace非常强烈，即使$ k = 2 $也是如此。
$\newcommand{\cala}{\mathcal{A}}$ In MAXSPACE, given a set of ads $\cala$, one wants to schedule a subset ${\cala'\subseteq\cala}$ into $K$ slots ${B_1, \dots, B_K}$ of size $L$. Each ad ${A_i \in \cala}$ has a size $s_i$ and a frequency $w_i$. A schedule is feasible if the total size of ads in any slot is at most $L$, and each ad ${A_i \in \cala'}$ appears in exactly $w_i$ slots and at most once per slot. The goal is to find a feasible schedule that maximizes the sum of the space occupied by all slots. We consider a generalization called MAXSPACE-R for which an ad $A_i$ also has a release date $r_i$ and may only appear in a slot $B_j$ if ${j \ge r_i}$. For this variant, we give a $1/9$-approximation algorithm. Furthermore, we consider MAXSPACE-RDV for which an ad $A_i$ also has a deadline $d_i$ (and may only appear in a slot $B_j$ with $r_i \le j \le d_i$), and a value $v_i$ that is the gain of each assigned copy of $A_i$ (which can be unrelated to $s_i$). We present a polynomial-time approximation scheme for this problem when $K$ is bounded by a constant. This is the best factor one can expect since MAXSPACE is strongly NP-hard, even if $K = 2$.
