Skip to main content
About HEC About HEC Faculty & Research Faculty & Research Master’s programs Master’s programs MBA Programs MBA Programs PhD Program PhD Program Executive Education Executive Education Summer School Summer School HEC Online HEC Online About HEC Overview Overview Who
We Are Who
We Are
Egalité des chances Egalité des chances HEC Talents HEC Talents International International Campus
Life Campus
Life
Sustainability Sustainability Diversity
& Inclusion Diversity
& Inclusion
Stories Stories The HEC
Foundation The HEC
Foundation
Coronavirus Coronavirus
Faculty & Research Overview Overview Faculty Directory Faculty Directory Departments Departments Centers Centers Chairs Chairs Knowledge Knowledge Master’s programs Master in
Management Master in
Management
Master in
International Finance Master in
International Finance
Specialized
Masters Specialized
Masters
Ecole Polytechnique
-HEC programs Ecole Polytechnique
-HEC programs
Dual-Degree
programs Dual-Degree
programs
Visiting
students Visiting
students
Certificates Certificates Student
Life Student
Life
MBA Programs MBA MBA Executive MBA Executive MBA TRIUM EMBA TRIUM EMBA PhD Program Overview Overview HEC Difference HEC Difference Program details Program details Research areas Research areas HEC Community HEC Community Placement Placement Job Market Job Market Admissions Admissions Financing Financing Executive Education Executive Masters Executive Masters Executive Certificates Executive Certificates Executive short programs Executive short programs Online Online Companies Companies Executive MBA Executive MBA Infinity Pass Infinity Pass Summer School Youth Programs Youth Programs Summer programs Summer programs HEC Online Overview Overview Degree Program Degree Program Executive certificates Executive certificates MOOCs MOOCs Summer Programs Summer Programs
Faculty & Research

Online Matching and Ad Allocation: A Random Graphs perspective

07 Dec
2022
10:00 am
Jouy-en-Josas
English

Participate

Add to Calendar
2022-12-07T10:00:00 2022-12-07T11:15:00 Online Matching and Ad Allocation: A Random Graphs perspective Information Systems and Operations Management Speaker: Flore Sentenac (ENSAE) Room Bernard Ramanantsoa Jouy-en-Josas

Information Systems and Operations Management

Speaker: Flore Sentenac (ENSAE)

Room Bernard Ramanantsoa

Abstract:
The theory of online matching in graphs received a gain of interest in recent years due to its application to ad allocation on the internet. A large body of work considered the problem in general classes of graphs, introducing algorithms with worst-case guarantees.
Beyond this worst-case approach, we study online matching in models of random graphs relevant to the ad allocation problem. In particular, we will look at the so-called configuration model and geometric random graphs.
We estimate the performance of the most straightforward algorithm, GREEDY, by approximating some relevant stochastic discrete processes by their continuous counterparts, which are solutions of an explicit system of partial differential equations. Thanks to these techniques, we theoretically highlight in which instances GREEDY far outperforms its worst-case guarantee. We can also explain how some graph characteristics, such as the degree distribution, affect the performance of the algorithm.

Participate

Add to Calendar
2022-12-07T10:00:00 2022-12-07T11:15:00 Online Matching and Ad Allocation: A Random Graphs perspective Information Systems and Operations Management Speaker: Flore Sentenac (ENSAE) Room Bernard Ramanantsoa Jouy-en-Josas