Speaker: |
Umang Bhaskar |

Organiser: |
Rahul Vaze |

Date: |
Friday, 17 Jul 2020, 14:00 to 15:00 |

Venue: |

(Scan to add to calendar)

We present an algorithm that for the general case of subadditive utility functions for the agents, obtains an $O(n)$-approximation to the optimal Nash Social Welfare, given value oracle access to the utility functions. This improves upon a previous $O(n log n)$ algorithm for submodular utilities (SODA '20). Our approximation ratio is tight for subadditive utilities and for value oracle access.

This is joint work with Siddharth Barman, Anand Krishna, and Ranjani Sundaram.