Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915637804138496 |
|---|---|
| author | Ali, Dildar Benerjee, Suman Prasad, Yamuna |
| author_facet | Ali, Dildar Benerjee, Suman Prasad, Yamuna |
| contents | We study the problem of minimizing regret in multi-mode advertisement settings, where an influence provider allocates advertising resources such as social network seeds and billboard slots to multiple advertisers with specified influence demands and payments. Unlike prior work focusing on a single mode of advertising, we consider the interplay between online and offline modes and introduce a novel regret model that captures their interaction effect. This leads to a regret minimization problem that is non-monotone, non-submodular, and NP-hard to approximate within any constant factor. To address this, we propose a monotone, approximately bisubmodular influence model and develop two algorithmic solutions: Projected Subgradient Method based on the Lovász extension of the regret function, and an Approximate Bisubmodular Local Search algorithm with provable guarantees. Experiments on large-scale real-world datasets, including billboard and trajectory data from major U.S. cities, as well as social network graphs, demonstrate that our methods outperform existing baselines in minimizing total regret while satisfying advertiser demands. Our framework is broadly applicable to other resource allocation scenarios beyond advertising. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09084 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising Ali, Dildar Benerjee, Suman Prasad, Yamuna Computer Science and Game Theory Databases Data Structures and Algorithms We study the problem of minimizing regret in multi-mode advertisement settings, where an influence provider allocates advertising resources such as social network seeds and billboard slots to multiple advertisers with specified influence demands and payments. Unlike prior work focusing on a single mode of advertising, we consider the interplay between online and offline modes and introduce a novel regret model that captures their interaction effect. This leads to a regret minimization problem that is non-monotone, non-submodular, and NP-hard to approximate within any constant factor. To address this, we propose a monotone, approximately bisubmodular influence model and develop two algorithmic solutions: Projected Subgradient Method based on the Lovász extension of the regret function, and an Approximate Bisubmodular Local Search algorithm with provable guarantees. Experiments on large-scale real-world datasets, including billboard and trajectory data from major U.S. cities, as well as social network graphs, demonstrate that our methods outperform existing baselines in minimizing total regret while satisfying advertiser demands. Our framework is broadly applicable to other resource allocation scenarios beyond advertising. |
| title | Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising |
| topic | Computer Science and Game Theory Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.09084 |