DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2026.3

Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization

Authors: Dildar Ali, Ansh Jasrotia, Abishek Salaria, and Suman Banerjee

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

How to utilize an allocated budget effectively for branding and promotion of a commercial house is an important problem, particularly when multiple advertising media are available. There exist multiple such media, and among them, two popular ones are billboards and social media advertisements. In this context, the question naturally arises: how should a budget be allocated to maximize total influence? Although there is significant literature on the effective use of budgets in individual advertising media, there are hardly any studies examining budget allocation across multiple advertising media. To bridge this gap, this paper introduces the Budget Splitting Problem in Billboard and Social Network Advertisement. We introduce the notion of interaction effect to capture the additional influence due to triggers from multiple media of advertising. Using this notion, we propose a noble influence function Φ(,) that captures the total influence and shows that this function is non-negative, monotone, and non-bisubmodular. We introduce bi-submodularity ratio (γ) and generalized curvature (α) to measure how close a function is to being bi-submodular and how far a function is from being modular, respectively. We propose the Randomized Greedy and Two-Phase Adaptive Greedy approach, where the influence function is non-bisubmodular and achieves an approximation guarantee of (1/α)(1-e^(-γα)). We conducted several experiments using real-world datasets and observed that the proposed solution approach’s budget splitting leads to a greater influence than existing approaches.

Cite as

Dildar Ali, Ansh Jasrotia, Abishek Salaria, and Suman Banerjee. Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ali_et_al:LIPIcs.SEA.2026.3,
  author =	{Ali, Dildar and Jasrotia, Ansh and Salaria, Abishek and Banerjee, Suman},
  title =	{{Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.3},
  URN =		{urn:nbn:de:0030-drops-260070},
  doi =		{10.4230/LIPIcs.SEA.2026.3},
  annote =	{Keywords: Advertisement, Billboard, Social Network, Bi-submodularity, Influence Maximization}
}

Document

DOI: 10.4230/DagRep.8.5.31

Inter-Vehicular Communication Towards Cooperative Driving (Dagstuhl Seminar 18202)

Authors: Onur Altintas, Suman Banerjee, Falko Dressler, and Geert Heijenk

Published in: Dagstuhl Reports, Volume 8, Issue 5 (2019)

Abstract

Looking back at the last decade, one can observe enormous progress in the domain of vehicular networking. In this growing community, many ongoing activities focus on the design of communication protocols to support safety applications, intelligent navigation, multi-player gaming and others. This seminar shifted the focus from basic networking principles to networked control applications. We were particularly interested in eSafety applications and traffic efficiency applications that are thought to yield substantial benefits for the emerging "cooperative automated driving" domain. The seminar brought together experts from several fields, including classical computer science (computer networking, simulation and modeling, operating system design), electrical engineering (digital signal processing, communication networks), and automated driving (mechanical engineering, image processing, control theory), to discuss the most challenging issues related to inter-vehicular communication and cooperative driving.

Cite as

Onur Altintas, Suman Banerjee, Falko Dressler, and Geert Heijenk. Inter-Vehicular Communication Towards Cooperative Driving (Dagstuhl Seminar 18202). In Dagstuhl Reports, Volume 8, Issue 5, pp. 31-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{altintas_et_al:DagRep.8.5.31,
  author =	{Altintas, Onur and Banerjee, Suman and Dressler, Falko and Heijenk, Geert},
  title =	{{Inter-Vehicular Communication Towards Cooperative Driving (Dagstuhl Seminar 18202)}},
  pages =	{31--59},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{5},
  editor =	{Altintas, Onur and Banerjee, Suman and Dressler, Falko and Heijenk, Geert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.5.31},
  URN =		{urn:nbn:de:0030-drops-98929},
  doi =		{10.4230/DagRep.8.5.31},
  annote =	{Keywords: automated driving, cooperative driving, road traffic safety, vehicular networking}
}

Search Results

Documents authored by Banerjee, Suman

Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization

Abstract

Cite as

Inter-Vehicular Communication Towards Cooperative Driving (Dagstuhl Seminar 18202)

Abstract

Cite as

Thanks for your feedback!

Could not send message