没有合适的资源?快使用搜索试试~ 我知道了~
−∈ A∈ A≤≤≥≤A A A.A.可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)699-710www.elsevier.com/locate/entcsMAXSPACE广告问题毛罗河C. da Silva1,2 Rafael C.S. Schouery1,3 LehiltonL.C. Pedrosa佩德罗萨1,4巴西坎皮纳斯大学计算机学院摘要在MAXSPACE问题中,给定一组广告,人们希望放置一个子集“插 入 K 个 插槽B1, . ,尺寸为L的BK。EachadAi具有大小S1和频率W1 。如果ny个时隙中的广告的总大小至多为L,并且每个广告A为“在正确的WI插槽中安装耳朵。 我们的目标是找到一个可行的时间表,最大化所有插槽占用的空间之和。 我们引入了一个泛化,称为MAXS PACE-RD,其中h c hadAi也有一个发布日期ri1and ad e adlin e diK和m只出现在时隙Bj中,其中riJ迪岛这些参数模拟的情况是,广告对应于具有可能在某个定义的时期之后到期的公告日期的商业活动。 我们提出了一个多项式时间近似方案MAXSPACE-RD时,K是有界的常数,即,对于任何ε >0,我们给出了一个多项式时间算法,该算法返回值为最少(1ε)Opt,其中Opt是最优值。 这是最好的因素,因为MAXSPACE是NP难的,即使K = 2。关键词:近似算法,PTAS,广告调度,MAXSPACE。1介绍许多网站(如Google,Yahoo!Facebook和其他公司)提供免费服务,同时向用户显示广告,或者仅仅是广告。通常,每个网站都有一个固定高度的单一条带,用于安排广告,并且显示的广告集会随时间变化。对于这些网站来说,广告是主要的收入来源。因此,重要的是要找到在可用时间和空间内放置广告的最佳方式,同时最大化收入[7]。1本项目得到新加坡保罗研究基金会(F APESP)资助#2015/11937-9、#2016/23552-7和#2017/21297-2,以及国 家 科 学 技 术 发 展 委 员 会 ( CNPq ) 资 助 #425340/2016-3 、 #313026/2017-3 、 #308689/2017-8 和#425806/2018-9。2电子邮件:maurorcsc@gmail.com3电子邮件:rafael@ic.unicamp.br4电子邮件:lehilton@ic.unicamp.brhttps://doi.org/10.1016/j.entcs.2019.08.0611571-0661/© 2019作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。700M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699≤jiA∈BijΣ232333K/w网络广告的收入在21世纪大幅增长2013年,总收入为427.8亿美元,较上年增长17%据估计,美国网络广告在2016年达到770亿美元,占所有广告支出的35%,超过电视广告[7]。2016年,横幅广告占互联网广告的31.4%(考虑横幅广告和移动平台),收入为227亿美元[8]。网络广告已经创造了一个亿万富翁的行业,在这个行业中,用于安排广告的算法发挥着重要作用。我们考虑Adler等人提出的广告调度问题。 [1],其中,给定集合A={A1,A2,., A n}的广告,目标是以K个相等的时间间隔将子集AJ= A调度到横幅中。被调度到特定时间间隔j(1≤j≤K)的广告集合由广告集合Bj<$AJ表示,其被称为时隙。每个广告Ai具有大小si和与其相关联的频率wi大小si表示Ai在时隙中占据的空间量,并且频率wi≤K表示应该包含Ai的副本的时隙的数量。一个广告Ai在一个时隙中最多只能显示一次,如果Ai的w i个副本出现在时隙中,每个时隙最多一个副本,则称Ai被调度[1,4]。该类中的主要问题是MINSPACE和MAXSPACE。在MINSPACE中,所有的广告都安排在广告位上,目标是最大限度地减少最高广告位的高度在MAXSPACE中,指定了一个上限L,它表示每个插槽的大小。该问题的可行解决方案是将子集AJ= A调度到时隙B1,B2,.,B K,使得每个A i∈ AJ被调度,并且任何时隙的充满度不超过上界L,即,对于每个时隙B,sL.MAXSPACE的目标是最大限度地提高slot,定义为Ai∈A'siwi。这两个问题都是强NP-hard问题[1,4]。Dawande等人[4]定义了MAXS-PACE的三种特殊情况:MAX w,MAX K|W和MAX S。在MAXw中,每个广告具有相同的频率w。 在MAX K中|w,每个ad具有相同的频率w,并且时隙的数量K是w的倍数。 而且,在MAXs中,每个广告都有相同的大小。以类似的方式,他们定义了MIN SPA CE 的三种特殊情况:MIN W,MIN K|w和MIN s。Adler等[1]提出了当广告大小序列为s1>s2>s3>时,MAXS-PACE的1 -近似SUBSET-LSLF。. . ,使得对于所有i,si是si+1的倍数。 Dawande等人 [4]提出了三种近似算法,MAXSPACE的(1+1)近似,MAXw的1近似和1-4 4K 3 2MAX K的近似值|W. Freund和Naor[6]提出了MAXSPACE的(1−ε)-近似和广告大小在区间[L/2,L]内的特殊情况的(1 − ε)-近似。Adler 等 [1] 提 出 了 一 个2- 近 似 称 为 最 大 尺 寸 最 小 满 ( LSLF ) 的MINSPACE。 算法LSLF也是一个(4-1)-近似最小K|w[4]。 Dawande等人[4]给出了MINSPACE的2-近似,LP Rouding,Dean和Goemans[5]提出了MINSPACE的4-近似用Graham在实践中,相对于调度广告中的每个时隙的时间间隔可以表示分钟、秒或长时段,诸如天和周。通常,一M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699701Σ解S为f(S)=Kjj=1 f(Bj).考虑发布日期和截止日期的想法。广告有一个发布日期,表明其广告活动的开始。类似地,广告指示其广告活动的结束。例如,圣诞节的广告必须安排在12月25日之前。我们引入了一个MAXSPACE推广,称为MAXSPACE-RD,其中每个广告Ai都有两个附加参数,发布日期ri≥1和截止日期di≤K。广告Ai的发布日期表示可以调度A i的副本的第一个时隙,即Ai的副本不能调度在具有j ri的时隙Bj中。类似地,广告Ai的最后期限表示我们可以调度Ai的副本的最后时隙,因此Ai不能在时隙Bj中调度,其中j >di。我们假设每个广告Ai的出现频率与其发布日期和截止日期相容,即di−ri+1≥wi。设问题是一个最大化问题。一个算法族{Hε}是一个多项式时间近似方案(PTAS),如果,对于每个常数ε>0,Hε是一个(1-ε)-近似[9]。全多项式时间近似方案(FPTAS)是一种PTAS,其运行时间也是1/ε多项式。在在这项工作中,我们提出了一个PTAS到MAXSPACE-RD时,槽数是一个常数这种近似是最好的,因为MAXSPACE是NP难的,即使插槽数是2 [1,4]。在第2节中,我们定义了这项工作中使用的符号和概念。在第3节中,我们提出了一个算法来安排小广告,在第4节中,我们提出了一个PTAS的整个广告集。在第5节中,我们讨论了结果和未来的工作。2预赛在 下 文 中 , 假 设 槽 的 数 量 K 是 常 数 , L= 1 , 并 且 对 于 每 个 Ai∈ A ,00时,我们说Ai是大AD,如果si≥ε/(22K 2KK),否则我们称之为K这是一个小广告。 设G ={A i∈A|s i≥ε/(2 2 2 KK)}是大广告的集合P=A\G是小广告的集合。令S表示调度到时隙B1,B2,...中的可行解A j ∈ A,B K.则槽B j的充满度定义为f(B j)=Ai∈Bjs i。此外,丰满Ai∈AJ的类型t 对于解S,是时隙的子集Ai被赋给它,即Ai∈Bj当且仅当j∈t。设T是包含所有槽子集的集合,则T包含所有可能的类型,|不|= 2 K。观察到两个相同类型的广告具有相同的频率,因此可以将所有相同类型的广告视为单个广告。对于每个t∈T,类型t的占用是具有该类型的广告在其每个槽中占用的空间,即,设AJt是A的子集,由ty p e t的ad组成,t e nt=Ai∈A′tsi.广告子集AJ的配置是调度AJ中的每个广告的可行解。引理2.1指出,如果K是常数,那么只包含大广告的可能配置的数量是大广告数量的多项式702M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699J.|Σ|Σ最OR,它是多项式,|G|因为R是常数。并且可以通过蛮力算法来枚举。引理2.1如果K是常数,则G可以在多项式时间内列出证据由于每个容器的高度为1,因此可以调度到单个时隙中的大型广告的数量至多为1/(ε/(2 2K 2 KK))=(2 2K 2 KK)/ε。则一个可行解最多可包含R=K(22 K2KK)/ε大ads.选择每个子集o。fGjG,|GJ| ≤R。观察到这样的子集的n个b是t对于每个GJ,创建一个多集M,其中每个adAi∈GJ出现wi次,并将M的每个分区列成集合B1,B2,.,B K. 以来|M| ≤KR有界由一个常数,这样的分区的数量为每个G是有界的常数。现在注意,GJ的任何可行解,如果有的话,都是M的一个划分。这就完成了引理。Q所谓的第一适应启发式算法是一种算法,它在第一个兼容的时段中迭代地调度引理2.2指出,如果最优值小于1/ 2,则第一拟合启发式是最优的。该结果用于第4节。引理2.2设Opt是A的最优解,f(Opt)<为1/2。第一个启发式算法调度整个集合A。证据首先,注意对每个Ai∈ A,si<1/2,因为否则我们只能安排Ai得到解SJ,使得f(SJ)≥ 1/2> f(Opt),这是矛盾的。为了矛盾起见,假设存在一个最优解Opt到A,f(Opt)为1/ 2,并且第一拟合启发式算法不调度整个集合A。<现在,设S是第一个启发式算法返回的解,设AJ是S调度的广告集。我们称AJ=A。如果不是,则算法必须在尝试调度广告Ai时停止。由于该算法考虑了发布日期和截止日期,因此一定是这样的情况,即Ai不能被添加到某个槽Bj而不超过容量。由于在 这 种 情 况 下 f ( Bj ) +si>1 , 且 si1/ 2 , 因 此 f ( Bj ) >1/ 2 。 但 是 f(S)>1/ 2> f(Opt),这是一个矛盾。Q3小广告引理2.1指出,所有大型项目的配置都可以在多项式时间内列出,因此可以猜测由最优解诱导的大型广告的配置。这表明,MAXSPACE的难点在于为小广告提供解决方案。在本节中,我们考虑MAXSPACE的一个变体,它只包含小广告,并为这个问题提供了一个几乎最优的算法从形式上讲, 让 ε>0被 一 恒定 等 的 1/ε为 一个 整数. 我们M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699703的1t1一个2t2一个3t3一个4..t2KΣεXyAmFig. 1. 将广告分配给类型的流程图示例。 蓝色的是U,绿色的是V。定义 小-最大间距-RD作为 的 问题 的, 给定 一 设置 的 广告P,K其中对于每个Ai∈P,siε/(22 2KK),对于每个类型t∈T,且inte-ger c t∈ {0,1,.,1/ε},我们希望对每个t ∈T找到一个子集AJt<$P,使得占用Ai∈A′tsi≤ctε,并且使充满度最大化Σ Σ|不|锡岛t∈TAi∈A′t这个问题背后的推理是,我们试图推断出每种类型在其任何插槽中所占据的空间。因此,对于每种类型,我们猜测ε的整数倍作为其容量。由于容器此外,由于有2K种类型,如果C是容量组合的集合,则C的大小为. 1万2千对于C中的每一个组合c,我们使用最大最小流算法创建广告到类型的分配。对于这一步,我们创建一个图H如下。H的顶点是源顶点x、宿顶点y,以及集合U和V,其中U包含每个ad的顶点,并且V包含每个类型的顶点。对于每个adAi∈P和每个类型t∈T,如果类型t中的时隙对应于adAi的有效调度,即t恰好包含wi个时隙,并且t的每个时隙都遵守Ai的发布日期和截止日期,则我们添加具有低容量∞的边(Ai,t)。此外,我们对每个Ai ∈ U添加一条具有低容量wi s i的边(x,Ai),以及一条具有容量wi s i的边(t,y|不|c t对于每个t∈T。图1显示了该图。然后考虑H中的最大xy-owF,它可以在多项式时间[2]中获得,注意F诱导从ads到类型的赋值。在该分配中,如果最大的k_low使得F Ai,t单元从ad A i到类型t k_low,则我们可以通过FAi,t/(wisi)的量将ad A i部分地分配给t。注意这个比例最多是1。FAi,t>0的所有类型t的集合称为Ai的支集,记为Sup(Ai)。为了消除分数分配,我们将广告分组为相同的支持。设W是类型的子集,PW是AdAi的集合,其中Sup(Ai)=W。特别地,每个adAi∈PW与任何类型t∈W相容。对于每个类型t∈W,我们|C|为.(一)704M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699ΣΣΣ2KAi∈PWAi∈PWt ∈Wt∈W将t从PW接收的总流量定义为zt=Ai∈PWFAi,t.通过PW中的每个ad被分数地分配给W中的类型,我们知道,w i s i≥换句话说,PW的总大小由下式给出:Ai∈PWwi si不小于类型W从PW接收的流。因此,我们可以移除PW中所有广告的分数分配,并将PW中的每个广告整体重新分配给W中的类型,丢弃任何剩余的广告。在算法1中总结了舍入分数分配的过程,其接收广告到类型W的分数分配作为输入,并返回整数分配。算法1用于舍入广告分配的算法1:程序舍入(F)2:对于每个Ai∈P和t∈T,3:FAJi,t←04:对于每个W5:PW←所有广告Ai,其中Sup(Ai)=W6:对于每个t∈W,7:zt←Ai∈PWFAi,t8:Zt←9:对于每个Ai∈PW,10:如果|不|f(Z t)+w i s i≤z t则11:Zt←Zt{Ai}12:FAJi,t←wisi13:PW←PW\{Ai}14:丢弃PW15:返回FJ我们观察到算法1在广告数量上是多项式的。引理3.1算法1在多项式时间内运行。引理3.2限制了算法1在每次迭代中丢弃的广告的总大小。引理3.2令W ∈ T,令PW是在算法开始时支持W的广告的集合。则执行后的总分配P W为ΣFAJi,t≥Ai,tK- -一种|W |ε/(22)。Ai∈PWt ∈WAi∈PWt∈WM.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699705ΣΣΣΣ||≤t∈WAi ∈Ztt∈WAi∈PWt ∈WJAi∈PWAi∈PWt ∈Wt∈WAi∈Pt∈TAi∈Pt∈TAi∈Pt∈TAi∈PWt ∈W证据 假设PW和zt与算法中的相同,并且回想一下,w i s i≥如果PW中没有ad被丢弃,则引理平凡地成立因此,假设存在在迭代中被丢弃的adAj由于Aj在第6行的每次迭代中都被丢弃,我们知道对于任何类型t,|f(Zt)+wjsj> zt.|f(Zt) +wjsj>zt.因此,我们认为,ΣFAJi,t=w i s i=|不|f(Z t)t∈W>(zt−wjsj)= Σ FAi,t−|W|wjsj.由于Aj是小的,sj<ε/(2 2K2 K),由于w≤K,引理如下。Q推论3.3由引理3.2得到。推论3.3最大分数阶导数与修正导数之间的差不大于ε。也就是说,FAJi,t≥FAi,t−ε。证据 考虑算法1的变量W和PW的值。使用引理3.2,我们有AJi,t=0AJi,t≥Σ⎛⎝ΣAi,t- -一种|W|ε/(22K2 K)εAi∈PWt∈W≥FAi∈P t∈TAi,t---2K(ε/(22K2K))=FAi,t−ε,Ai∈P t ∈T其中最后一个不等式成立,因为W2 K,最后一个等式成立,因为有2个|不|= 2 2K不同的选择W。Q小广告的完整算法在算法2中给出。给定参数ε>0,该算法接收一组小广告P和包含每种类型的容量的向量c作为输入。该算法在K个时隙中返回PjP的可行调度基于向量c,该算法创建一个最小流图,并执行一个最大最小流算法来分配广告类型。 算法舍入Ai∈PWt ∈W706M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699←←ΣAi∈Pt∈TAi∈Pt∈T将分数赋值转换为整数赋值。请注意,此分配可以很容易地转换为SMALL-MAXSPACE-RD的解决方案算法2小广告的算法。1:程序ALG Pε(P,c)2:H←使用c的值创建流程图3:FMAX F低(H)4:FJROUDING(F)5:根据积分赋值FJ创建解SJ6:返回SJ在引理3.4和引理3.5中,我们证明了算法2在实例大小上是多项式的,并且它最多丢弃最优调度的空间ε引理3.4算法2在多项式时间内执行。引理3.5设S P为溶液算法2 返回和让选择P 是一个最优的解决方案,为小-最大空间-RD为一个集P的 广告.则f(S P)≥ f(Opt P)− ε。证据设F是H中的一个极大值,FJ是舍入的输出.德费恩f(F)=FAi,t和f(FJ)=FAJi,t。观察到OptP诱导了H的一个值为f(OptP)的可行流这意味着f(F)≥f(OptP),因为F是一个最大的多项式。此外,注意f(SP)=f(FJ),则使用推论3.3,我们有f(S P)= f(F J)≥ f(F)− ε ≥ f(Opt P)− ε。Q4一般情况在下文中,我们推导出一般情况下的PTAS,该PTAS处理小型和大型广告。考虑最优解Opt,其将广告A的子集调度到时隙B1、B2、… ,BK. 请注意,Opt将大广告SG的可行配置引入插槽B1,B2,...,B K使得B j= B jG。由于引理2.1可以在多项式时间内列出所有候选配置,我们可以假设我们猜测了由Opt诱导的大型广告的配置SG。我们剩下的问题是放置小广告。对于每个时隙j,1≤j≤k,大广告未使用的空间为uj= 1−Ai∈Bj锡岛M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699707Σ虽然这些值并不完全指定每个类型t的容量ct,这是SMALL-MAXSPACE-RD的输入的一部分,但可能的容量可能性的数量是由等式(1)定义的常数,因此,我们可以再次猜测向量c。我们说一个向量c与SG相容,如果对于每个1 ≤j≤ K,c t ε ≤ u j.t∈T:j∈t设OPT是在解Opt中具有t的小的a的捕获。 我们证明了最优解诱导出一个与SG相容的向量c,并且对于每个c h t y p e t,ctε ≥ot−ε。 由于我们尝试了每个ch容量向量,我们可以假设我们猜测c并使 用 c 求解了SMALL-MAXSPACE-RD的实例。给定参数ε>0,算法3接收一组广告A作为输入,并返回一个可行解。首先,该算法尝试使用第一个合适的启发式算法来调度所有广告,如果可能,则返回解决方案。否则,对于大广告SG的每个配置和与SG兼容的每个容量向量c,算法调用算法ALGPε并获得小广告SP的调度。通过将SG中的大型广告解决方案与SP中的小型广告解决方案相结合,它得到问题的一个可行解S。该算法返回在所有配置和容量向量对中找到的最佳解Smax。算法3A用于整个广告集合的PTAS A.1:程序ALG(A,ε)2:使用first-fit创建解Smax3:如果Smax调度整个集合A,则4:返回SmaxK5:G ={A i∈A|s i≥ε/(2 22 KK)}6:P←A \G7:R←枚举大广告的配置集合,如引理2.1所示8:对于每个SG∈R,9:C←枚举与SG兼容的容量向量c的集合10:对于每个c∈C,11:SP←ALG Pε(P,c,ε)12:S←SGSP13:如果f(S)> f(Smax),则14:Smax←SJ15:返回Smax我们证明了算法3是一个PTAS。首先,引理4.1显示算法3在实例大小的时间多项式中运行。然后,引理4.2强调返回的解是可行的。引理4.1当K为常数时,算法3在多项式时间内执行。引理4.2算法3返回可行解。708M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699j∈tΣ∗J∗≥∈A∩′ijttA∈ Ait不Σ证据由于大型广告的每种配置都是可行的,因此SG尊重发布日期和截止日期的限制。由算法ALG Pε返回的解决方案SP也尊重对小广告的发布日期和截止日期限制。因此,只需要表明,对于SG和SP的并集,不超过每个时隙容量的容量。实际上,考虑1≤j≤K,并且令Bj是由SG调度的大广告的时隙。此外,设AJt是由SP调度的具有类型t的小广告的集合。则组合解中的槽j的占用我的世界si≤si+ctε≤si+uj≤1,Ai∈Bjt∈T:Ai∈A′tAi∈Bjt∈T:j∈tAi∈Bj其中,第一个不等式成立,因为SP是具有向量c的SMALL-MAXSPACE-RD的可行解,第二个不等式成立,因为c与SG相容。Q定理4.3算法3是具有常数K的MAXSPACE-RD的PTAS。证据通过引理4.1和引理4.2,算法在多项式时间内执行并返回可行解。设Opt是最优调度,并且设Smax是由Al-出租m 3返回的调度。 如果第一个启发式算法调度整个集合A,f(S max)= f(Opt),证明结束。因此,假设算法继续,并且根据引理2.2,f(Opt)≥1/ 2。用yA表示yOpt所表示的ads的集合,设SGJ 和SPJ B.确认,分别由AβG和AβP诱导的大和小广告的产生,使得f(Opt) =f(SGJ)+f(SPJ)。此外,设CJ是容量向量,使得对于每个类型的pet,CJt是整数中最大的整数,其中CJtε ≤0,其中0是广告在A中的占用率,其中t是pet。 显然,cJt与SGJ兼容。因此,该算法构造一个解SJ,用于配置对SGJ 以及电容矢量CJ。设OptP是具有ads P 和向量cj 的SMALL-MAXSPACE-RD 的最优解。设f(OptP)≥f(SPJ)−2·2 KKε. 为了证明这一点,对于类型t,设AJt是具有类型t的AjP中的广告的最大子集,并且使得Ai∈A′ts i≤ cJtε。因此,集合AJt形成可行解SPJ J 适用于SMALL-MAXS PACE-RD,向量CJ。 因为AJt是最大的,要么AJt包含Ap中所有类型为t的并且s =oc ε,或者存在一个小的t型adAP,它不能被e加到o AJt上,并且<$Ai∈A′tsi>CJtε −sj。无论哪种情况,SIAi∈A′t>cJε − ε/(2 2K 2 KK)。M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699709j>(|不|c ε −|不|ε/(22K))KUANGYUANG>(|不|(o−ε)−|不|ε/(22 K))PK这意味着OptP的充满度,其至少是SPJJ的充满度,f(OptP)≥f(SPJJ)=0|不|SIt∈TAi∈A′t2KK不t∈T2K不t∈T≥f(SJ)− 2 KK(ε + ε/(2 2K 2 KK))。因此,f(OptP)≥f(SPJ)−2·2 KKε确实成立。如果SP是通过算法ALG Pε对向量cJ获得的解,则通过引理3.5,f(SP)≥f(OptP)−ε。设SJ是由combin考虑的解ingSGJ和SP。 由于该算法返回最佳的解决方案,f(Smax)≥f(SJ)=f(SGJ) +f(SP)≥f(SGJ) +f(OptP)−ε≥f(SGJ) +f(SPJ)−2· 2KKε−εK≥f(Opt)−3· 2Kε≥f(Opt)−6· 2Kε·f(Opt)=(1− 6· 2KKε)f(Opt),其中第四个不等式成立,因为2· 2KK> 1,最后一个不等式成立,因为f(Opt)>1/ 2。对于任何εJ>0,通过令ε=εJ/(6· 2KK),得到的解至少有(1−εJ)f(Opt)的充满度。因此,算法3是MAXSPACE-RD的PTASQ5最后发言本文提出了一个用于MAXSPACE-RD的PTAS,它是MAXSPACE的一个推广,用于处理发布日期和截止日期。据我们所知,这是该MAXSPACE变体的第一个近似方案。当输入中给定bin的数量时,我们可以证明MAXSPACE-RD是强NP难的,因此不允许FPTAS。我们留下了开放的问题,是否有一个固定数量的插槽的问题承认一个FPTAS。在未来的工作中,我们将考虑在输入中给出广告价值的变体,并且可能与其大小无关。这个变体是多背包问题[3]的推广,即使对于K= 2,它也是强NP困难的。引用[1] M. Adler,P. B. Gibbons和Y.马蒂亚斯安排互联网广告的空间共享。Journalof Scheduling,5(2):103710M.R.C. da Silva等人/理论计算机科学电子笔记346(2019)699K[2] R. K. Ahuja. 网络流:理论、算法与应用。Pearson Education,2017.[3] C. Chekuri和S.卡纳多背包问题的一个多项式时间近似格式。SIAM Journalon Computing,35(3):713[4] M. Dawande,S. Kumar,和C.斯里干达拉贾网页广告排程演算法之效能界限。Journal of Scheduling,6(4):373[5] B. C. Dean 和 M. X. 哥 曼 人 最 小 空 间 广 告 排 程 之 改 良 近 似 演 算 法 。 InProceedings of InternationalColloquium on Automata , Languages , andProgramming,pages 1138 -1152,2003.[6] A. Freund和J.S. Naor.近似的广告投放问题。在Proceedings of InternationalConference on Programming and Combinatorial Optimization,第415-424页, 2 0 0 2 年 。[7] S. 库玛网络和移动广告的优化问题:过去和未来的趋势。施普林格,2015年。[8] D.西尔弗曼互联网广告收入报告。在互动广告局的会议记录中。纽约,2010年,第26页。[9] 诉诉瓦齐拉尼近似算法。Springer Science Business Media,2013.一 遗漏的证据证据第4行和第6行的循环执行恒定次数的迭代,因为|不|=2 K,T的子集数为22。 内部循环(第9行)执行多项式次数的迭代,因为|P W|是多项式。然后,算法在多项式时间内执行Q证据[引理3.4]在图H[2]的大小中,最大的最小流是在多项式时间内求解的,并且H在实例的大小中是多项式的,因为它对于每个小ad恰好有一个顶点,并且对于类型有常数数量的顶点。根据引理3.1,ROUDING算法也是多项式的。然后,算法2是多项式的实例大小。Q证据根据引理2.1,大广告的配置数是多项式。因此,第8行的循环执行多项式次数的迭代。此外,根据等式(1),与每个这样的配置兼容的容量向量的数量因此,第10行的循环执行多项式次数的迭代。根据引理3.4,对A LG Pε的调用也在多项式时间内运行。 因此,该算法在多项式时间内运行。Q
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC关键绩效财务与客户指标详解
- 绘制企业战略地图:从财务到客户价值的六步法
- BSC关键绩效指标详解:财务与运营效率评估
- 手持移动数据终端:常见问题与WIFI设置指南
- 平衡计分卡(BSC):绩效管理与战略实施工具
- ESP8266智能家居控制系统设计与实现
- ESP8266在智能家居中的应用——网络家电控制系统
- BSC:平衡计分卡在绩效管理与信息技术中的应用
- 手持移动数据终端:常见问题与解决办法
- BSC模板:四大领域关键绩效指标详解(财务、客户、运营与成长)
- BSC:从绩效考核到计算机网络的关键概念
- BSC模板:四大维度关键绩效指标详解与预算达成分析
- 平衡计分卡(BSC):绩效考核与战略实施工具
- K-means聚类算法详解及其优缺点
- 平衡计分卡(BSC):从绩效考核到战略实施
- BSC:平衡计分卡与计算机网络中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)