Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs

Po-An Chen*, Ya Wen Cheng, Yao Wei Tseng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Gionis et al. have already proposed a greedy algorithm and some heuristics for the opinion maximization problem. Unlike their approach, we adopt mathematical programming to solve the opinion maximization problem on specific classes of networks. We find that on directed acyclic graphs, opinion influence between nodes will not cycle, but would spread outwards from influencers. Based on such an insight, we model the problem as a mixed integer programming (MIP) problem and relax the MIP to a linear program (LP). With MIP, we obtain optimal solutions for the opinion maximization problem and derive approximation solutions with LP randomized rounding algorithms. We conduct experiments for one LP randomized rounding algorithm and give an analysis of the approximation ratio for the other LP randomized rounding algorithm.

Original languageEnglish
Title of host publicationComplex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021
EditorsRosa Maria Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis M. Rocha, Marta Sales-Pardo
PublisherSpringer Science and Business Media Deutschland GmbH
Pages867-878
Number of pages12
ISBN (Print)9783030934088
DOIs
StatePublished - 2022
Event10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021 - Madrid, Spain
Duration: 30 Nov 20212 Dec 2021

Publication series

NameStudies in Computational Intelligence
Volume1015
ISSN (Print)1860-949X
ISSN (Electronic)1860-9503

Conference

Conference10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021
Country/TerritorySpain
CityMadrid
Period30/11/212/12/21

Keywords

  • Directed acyclic graphs
  • LP randomized rounding
  • Mixed integer programming
  • Opinion maximization

Fingerprint

Dive into the research topics of 'Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs'. Together they form a unique fingerprint.

Cite this