TY - JOUR

T1 - The max-out min-in problem

T2 - A tool for data analysis

AU - Cerdeira, Jorge Orestes

AU - Martins, Maria João

AU - Raydan, Marcos

N1 - info:eu-repo/grantAgreement/FCT/3599-PPCDT/PTDC%2FCCI-BIO%2F4180%2F2020/PT#
info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00239%2F2020/PT#
Funding Information:
The first and third authors were financially supported by the Fundação para a Ciência e a Tecnologia, Portugal (Portuguese Foundation for Science and Technology) through the projects UIDB/MAT/00297/2020 , UIDP/MAT/00297/2020 (Centro de Matemática e Aplicações).
Publisher Copyright:
© 2023 The Author(s)

PY - 2023/6

Y1 - 2023/6

N2 - Consider a graph with vertex set V and non-negative weights on the edges. For every subset of vertices S, define ϕ(S) to be the sum of the weights of edges with one vertex in S and the other in V∖S, minus the sum of the weights of the edges with both vertices in S. We consider the problem of finding S⊆V for which ϕ(S) is maximized. We call this combinatorial optimization problem the max-out min-in problem (MOMIP). In this paper we (i) present a linear 0/1 formulation and a quadratic unconstrained binary optimization formulation for MOMIP; (ii) prove that the problem is NP-hard; (iii) report results of computational experiments on simulated data to compare the performances of the two models; (iv) illustrate the applicability of MOMIP for two different topics in the context of data analysis, namely in the selection of variables in exploratory data analysis and in the identification of clusters in the context of cluster analysis; and (v) introduce a generalization of MOMIP that includes, as particular cases, the well-known weighted maximum cut problem and a novel problem related to independent dominant sets in graphs.

AB - Consider a graph with vertex set V and non-negative weights on the edges. For every subset of vertices S, define ϕ(S) to be the sum of the weights of edges with one vertex in S and the other in V∖S, minus the sum of the weights of the edges with both vertices in S. We consider the problem of finding S⊆V for which ϕ(S) is maximized. We call this combinatorial optimization problem the max-out min-in problem (MOMIP). In this paper we (i) present a linear 0/1 formulation and a quadratic unconstrained binary optimization formulation for MOMIP; (ii) prove that the problem is NP-hard; (iii) report results of computational experiments on simulated data to compare the performances of the two models; (iv) illustrate the applicability of MOMIP for two different topics in the context of data analysis, namely in the selection of variables in exploratory data analysis and in the identification of clusters in the context of cluster analysis; and (v) introduce a generalization of MOMIP that includes, as particular cases, the well-known weighted maximum cut problem and a novel problem related to independent dominant sets in graphs.

KW - Cluster analysis

KW - Combinatorial optimization

KW - Computational complexity

KW - Quadratic programming

KW - Variable selection

KW - Weighted graphs

UR - http://www.scopus.com/inward/record.url?scp=85150153286&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2023.106218

DO - 10.1016/j.cor.2023.106218

M3 - Article

AN - SCOPUS:85150153286

SN - 0305-0548

VL - 154

JO - Computers and Operations Research

JF - Computers and Operations Research

M1 - 106218

ER -