Online advertising assignment problem without free disposal
- Kim, Gwang Moon, Il-Kyeong
- Issued Date
- Online bipartite matching Online algorithms Deterministic algorithm Stochastic programming Benders decomposition
- This paper presents an online advertising assignment problem that generalizes the online version of the bipartite matching problem. Specifically, it focuses on the Display Ads problem, which is a generalization of the edge-weighted and capacitated matching problem. The display ads problem has been studied alongside the property of free disposal, in which an advertisement is allowed to be matched more times than its capacity. Although the problem with free disposal is tractable, the problem situation might be restricted and challenging to apply to other types of problems. The objective of this research on the display ads problem is to maximize the total weight of matched edges while considering a strict capacity constraint. This paper analyzes two online input orders (adversarial and probabilistic orders) to the problem. For the adversarial order, we design deterministic algorithms with worst-case guarantees and prove the competitive ratios of them. Upper bounds for the problem are also proposed. For the probabilistic order, stochastic online algorithms, consisting of scenario-based stochastic programming and Benders decomposition, are presented. We conduct numerical experiments of the stochastic online algorithm in two probabilistic order models (known IID and random permutation).
- Authorize & License
- Files in This Item:
Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.