Approximate Modularity and Sub-Modularity
DATE: 19 September
PLACE: Meeting room, 8th floor, Via Celoria 18
SPEAKER: Flavio Chierichetti
HOST: Paolo Boldi
A set function is approximately modular if it satisfies each modularity constraint to within an additive error.
In particular, the theory of approximate modularity is the set analogue of the Hyers-Ulam theory of approximately linear functions on convex domains.
In the talk, we will start by considering the problem of how close, in additive error, approximately modular functions are to modular functions; we will then move on to the problem of efficiently recovering a close modular function to an approximately submodular one.
This latter problem has applications in selecting which ads to show to users of an online advertisement platform, in order to maximize its expected revenue.
In the second part of the talk, we will consider similar questions in the setting of approximately submodular functions.
[Joint work with subsets of: Abhimanyu Das (Google), Anirban Dasgupta (IIT Gandhinagar), Ravi Kumar (Google)]