CHOSUN

Online advertising assignment problem without free disposal

Metadata Downloads
Author(s)
Kim, Gwang Moon, Il-Kyeong
Issued Date
2020-08
Keyword
Online bipartite matching Online algorithms Deterministic algorithm Stochastic programming Benders decomposition
Abstract
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).
Alternative Author(s)
김광 문일경
Department
Division of Business
Publisher
Elsevier
Citation
Kim, Gwang. (2020-08). Online advertising assignment problem without free disposal. Applied Soft Computing, 93(2), 10.1016/j.asoc.2020.106370
Type
Journal paper
ISSN
1568-4946
DOI
10.1016/j.asoc.2020.106370
URI
https://oak.chosun.ac.kr/handle/2020.oak/18977
Appears in Collections:
Division of Business > Kim, Gwang
Authorize & License
  • AuthorizeOpen
Files in This Item:
  • There are no files associated with this item.

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.