2026-04-14T08:50:22Zhttps://recercat.cat/oai/request

oai:recercat.cat:10459.1/4631812025-09-15T18:40:13Zcom_2072_3622col_2072_479130

Approximate and Optimal Solutions for the Bipartite Polarization Problem Alsinet, Teresa Argelich Romà, Josep Béjar Torres, Ramón Martínez Rodríguez, Santi Social Networks Polarization Combinatorial Optimization In a recent work we introduced a problem about finding the highest polarized bipartition on a weighted and labeled graph that represents a debate developed trough some social network, where nodes represent user’s opinions and edges agreement or disagreement between users. Finding this target bipartition is an optimization problem that can be seen as a generalization of the maxcut problem, so we first introduced a basic local search algorithm to find approximate solutions of the problem. In this paper we go one step further, and we present an exact algorithm for finding the optimal solution, based on an integer programming formulation, and compare the performance of a new variant of our local search algorithm with the exact algorithm. Our results show that at least on real instances of the problem, obtained from Reddit debates, the approximate solutions obtained are almost always identical to the optimal solutions. This work was partially funded by Spanish Project PID2019- 111544GB-C22 (MINECO / FEDER), by the European Union’s Horizon 2020 Research and Innovation Program under Grant Agreements 723596, 768824, 764025 and 814945, and by 2017 SGR 1537. 2022-10-17 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion https://doi.org/10.3233/FAIA220309 9781643683263 09226389 https://hdl.handle.net/10459.1/463181 eng info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-111544GB-C22/ES/SISTEMAS DE INFERENCIA PARA INFORMACION INCONSISTENTE: ANALISIS ARGUMENTATIVO/ Reproducció del document publicat a http://doi.org/10.3233/FAIA220309 Frontiers in Artificial Intelligence and Applications, 2022, vol. 356, p. 17-24, 24th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2022, Sitges, 19-21 octubre 2022 Frontiers in Artificial Intelligence and Applications info:eu-repo/grantAgreement/EC/H2020/723596/EU/Innova MicroSolar info:eu-repo/grantAgreement/EC/H2020/768824/EU/HYBUILD info:eu-repo/grantAgreement/EC/H2020/764025/EU/SWS-HEATING info:eu-repo/grantAgreement/EC/H2020/814945/EU/SolBio-Rev cc-by-nc, (c) Alsinet et al., 2022 cc-by-nc, (c) IOS Press, 2022 Attribution-NonCommercial 4.0 International info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by-nc/4.0/ IOS Press