التفاصيل البيبلوغرافية
| العنوان: |
A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem. |
| المؤلفون: |
da Silva, Mauro R.C., Schouery, Rafael C.S., Pedrosa, Lehilton L.C. |
| المصدر: |
ENTCS: Electronic Notes in Theoretical Computer Science; Aug2019, Vol. 346, p699-710, 12p |
| مصطلحات موضوعية: |
ADVERTISING, POLYNOMIAL time algorithms, BUSINESS announcements, COMPUTER algorithms, APPROXIMATION algorithms |
| مستخلص: |
In the MAXSPACE problem, given a set of ads A , one wants to place a subset A ′ ⊆ A into K slots B 1 ,..., B K of size L. Each ad A i ∈ A 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 ∈ A ′ appears in exactly w i slots. The goal is to find a feasible schedule which maximizes the sum of the space occupied by all slots. We introduce a generalization, called MAXSPACE-RD, in which each ad A i also has a release date r i ≥ 1 and a deadline d i ≤ K , and may only appear in a slot B j with r i ≤ j ≤ d i. These parameters model situations where a subset of ads corresponds to a commercial campaign with an announcement date that may expire after some defined period. We present a polynomial-time approximation scheme for MAXSPACE-RD when K is bounded by a constant, i.e., for any ε > 0, we give a polynomial-time algorithm which returns a solution with value at least (1 −ε) Opt , where Opt is the optimal value. This is the best factor one can expect, since MAXSPACE is NP-hard, even if K = 2. [ABSTRACT FROM AUTHOR] |
|
Copyright of ENTCS: Electronic Notes in Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Supplemental Index |
Full Text Finder