Skip to main content
About HEC About HEC
Summer School Summer School
Faculty & Research Faculty & Research
Master’s programs Master’s programs
Bachelor Programs Bachelor Programs
MBA Programs MBA Programs
PhD Program PhD Program
Executive Education Executive Education
HEC Online HEC Online
About HEC
Overview Overview
Who
We Are
Who
We Are
Égalité des chances Égalité des chances
HEC Talents HEC Talents
International International
Sustainability Sustainability
Diversity
& Inclusion
Diversity
& Inclusion
The HEC
Foundation
The HEC
Foundation
Campus life Campus life
Activity Reports Activity Reports
Summer School
Youth Programs Youth Programs
Summer programs Summer programs
Online Programs Online Programs
Faculty & Research
Overview Overview
Faculty Directory Faculty Directory
Departments Departments
Centers Centers
Chairs Chairs
Grants Grants
Knowledge@HEC Knowledge@HEC
Master’s programs
Master in
Management
Master in
Management
Master's
Programs
Master's
Programs
Double Degree
Programs
Double Degree
Programs
Bachelor
Programs
Bachelor
Programs
Summer
Programs
Summer
Programs
Exchange
students
Exchange
students
Student
Life
Student
Life
Our
Difference
Our
Difference
Bachelor Programs
Overview Overview
Course content Course content
Admissions Admissions
Fees and Financing Fees and Financing
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
FAQ FAQ
Executive Education
Home Home
About us About us
Management topics Management topics
Open Programs Open Programs
Custom Programs Custom Programs
Events/News Events/News
Contacts Contacts
HEC Online
Overview Overview
Executive programs Executive programs
MOOCs MOOCs
Summer Programs Summer Programs
Youth programs Youth programs
Faculty & Research

Online Matching and Ad Allocation: A Random Graphs perspective

07 Dec
2022
10:00 am - 11:15 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