## Abstract

Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/ϵ) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam [11] to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu [12] to 0.7299. We also consider two extensions, one is "known I.I.D." with non-integral arrival rate and stochastic rewards; the other is "known I.I.D." b-matching with non-integral arrival rate and stochastic rewards. We present a simple non-adaptive algorithm which works well simultaneously on the two extensions. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution f; however, these give us less control over the structure of f. We next remove all these additional constraints and randomly move from f to a feasible point on the matching polytope with all coordinates being from the set {0, 1/k,2/k,⋯,1} for a chosen integer k. The structure of this solution is inspired by Jaillet and Lu (Mathematics of Operations Research, 2013) and is a tractable structure for algorithm design and analysis. The appropriate random move preserves many of the removed constraints (approximately [exactly] with high probability [in expectation]). This underlies some of our improvements, and, we hope, could be of independent interest.

Original language | English (US) |
---|---|

Title of host publication | 24th Annual European Symposium on Algorithms, ESA 2016 |

Editors | Christos Zaroliagis, Piotr Sankowski |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770156 |

DOIs | |

State | Published - Aug 1 2016 |

Externally published | Yes |

Event | 24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, Denmark Duration: Aug 22 2016 → Aug 24 2016 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 57 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 24th Annual European Symposium on Algorithms, ESA 2016 |
---|---|

Country/Territory | Denmark |

City | Aarhus |

Period | 8/22/16 → 8/24/16 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Ad-Allocation
- Online matching
- Randomized algorithms