2026-07-21T12:18:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24376 2025-12-12T15:01:12Z ddc:004 open_access

Improved Approximation Guarantees for Advertisement Placement Gálvez, Waldo Oliva, Roberto Verdugo, Victor Advertisement Placement Two-dimensional Packing Geometric Knapsack Resource Allocation The advertisement placement problem involves selecting and scheduling ads within a timeline that has capacity constraints to maximize profit. Each task is characterized by its height, width, and profit, and must be fully scheduled across multiple time slots. This problem models practical scenarios such as internet advertising and energy management, and it also generalizes classical combinatorial optimization problems like the knapsack and bin packing problems. We present a simple (2+ε)-approximation algorithm for any ε > 0, which improves upon the state-of-the-art 3+ε factor established by Freund and Naor twenty years ago. Our approach combines rounding techniques with dynamic programming and an efficient extension of list scheduling. Furthermore, we enhance this method with linear programming techniques to provide an almost optimal (1+ε)-approximation algorithm under resource augmentation, which allows for a slight increase in time slot capacities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Waldo Gálvez and Roberto Oliva and Victor Verdugo 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.10 urn:nbn:de:0030-drops-243762 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode