A dynamic learning algorithm for online matching problems with concave returns

Xiao Alison Chen, Zizhuo Wang

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We consider an online matching problem with concave returns. This problem is a generalization of the traditional online matching problem and has vast applications in online advertising. In this work, we propose a dynamic learning algorithm that achieves near-optimal performance for this problem when the inputs arrive in a random order and satisfy certain conditions. The key idea of our algorithm is to learn the input data pattern dynamically: we solve a sequence of carefully chosen partial allocation problems and use their optimal solutions to assist with the future decisions. Our analysis belongs to the primal-dual paradigm; however, the absence of linearity of the objective function and the dynamic feature of the algorithm makes our analysis quite unique. We also show through numerical experiments that our algorithm performs well for test data.

Original languageEnglish (US)
Pages (from-to)379-388
Number of pages10
JournalEuropean Journal of Operational Research
Volume247
Issue number2
DOIs
StatePublished - Dec 1 2015

Bibliographical note

Funding Information:
We thank the anonymous referees for their insightful comments. The research of both authors is supported by National Science Foundation under research grant CMMI-1434541 .

Publisher Copyright:
© 2015 Elsevier B.V. and Association of European Operational Research Societies(EURO)with in the International Federation of Operational Research Societies(IFORS).All rights reserved.

Keywords

  • Adwords problem
  • Dynamic price update
  • Online algorithms
  • Primal-dual
  • Random permutation model

Fingerprint

Dive into the research topics of 'A dynamic learning algorithm for online matching problems with concave returns'. Together they form a unique fingerprint.

Cite this