2
$\begingroup$

Consider a graph $G = (V,E)$ where $V$ is the set of vertices and $E$ is the set of weighted edges. We want to create $N$ disjoint subsets of $V$ such that the sum of weights inside each subset is maximised whereas the sum of weights that are connecting two different subsets is minimised. The $N$ needs to be determined and it's not given upfront. It's part of the solution.

For example, given a graph $G$ with 5 vertices. I decide to split into two parts the first one contains vertices 1,2 and 3 and the second one contains 4 and 5. My split maximises the sum of weights on green edges and minimises the sum of weights on red edges

Notice that the number $N$ of subsets is part of the decision.

Is this a well-defined optimization problem? It's some variation of a graph partitioning problem, but Is there a more precise name that commonly used name for it? Is there some papers about solving it?

$\endgroup$
5
  • $\begingroup$ Are the weights nonnegative? Is there any restriction on $N$? $\endgroup$
    – RobPratt
    Commented Aug 28, 2023 at 0:42
  • $\begingroup$ There is no restriction on $N$. Your question on the weights is interesting. I am interested to see your answer in both cases: weights in $\mathbb{N}$ and $\mathbb{Z}$ $\endgroup$ Commented Aug 28, 2023 at 1:19
  • 1
    $\begingroup$ If the weights are nonnegative, take $N=1$, with the entire vertex set $V$ in one part. $\endgroup$
    – RobPratt
    Commented Aug 28, 2023 at 1:26
  • $\begingroup$ Ok you're right, I think it needs to be $N>1$. Let's assume that weights are non negative, the worst case is when $ N = |V|$. All edges are connecting different subsets. $\endgroup$ Commented Aug 28, 2023 at 2:01
  • $\begingroup$ This is not far from the capacitated clustering problem $\endgroup$
    – fontanf
    Commented Aug 28, 2023 at 6:04

1 Answer 1

1
$\begingroup$

What you are looking for sounds like a variant of the HUB-location allocation problem, specifically, Uncapacitated Multiple Allocation Hub Location Problem. This problem contains a graph $G = (V, E)$ where there are some disjoint subsets or HUBs that need to be located and some demand points that should be allocated to each hub. The number of hubs/disjoint subsets may be either predetermined or a decision variable. Also, the objective function can be a single form or also multi-objective. In your case, as the objectives have different directions it seems to be the second form.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.