The max-out min-in problem: A tool for data analysis

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
15 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article number106218
Number of pages11
JournalComputers and Operations Research
Volume154
DOIs
Publication statusPublished - Jun 2023

Keywords

  • Cluster analysis
  • Combinatorial optimization
  • Computational complexity
  • Quadratic programming
  • Variable selection
  • Weighted graphs

Fingerprint

Dive into the research topics of 'The max-out min-in problem: A tool for data analysis'. Together they form a unique fingerprint.

Cite this