@inproceedings{34a2a519285349aaa6c40507daf5bf7c,
title = "Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs",
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.",
keywords = "Directed acyclic graphs, LP randomized rounding, Mixed integer programming, Opinion maximization",
author = "Po-An Chen and Cheng, {Ya Wen} and Tseng, {Yao Wei}",
note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; null ; Conference date: 30-11-2021 Through 02-12-2021",
year = "2022",
doi = "10.1007/978-3-030-93409-5_71",
language = "English",
isbn = "9783030934088",
series = "Studies in Computational Intelligence",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "867--878",
editor = "Benito, {Rosa Maria} and Chantal Cherifi and Hocine Cherifi and Esteban Moro and Rocha, {Luis M.} and Marta Sales-Pardo",
booktitle = "Complex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021",
address = "Germany",
}