Skip to main content
MathOverflow

Return to Question

formatting, added tag
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Clustering of vertices in an n dimensional$n$-dimensional cube

Consider the vertices of an n$n$-dimensional cube. DistanceThe distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call the total set of vertices as 'T'$T$ and the subset as 'S'$S$ then our objectivepurpose is to partition 'S'$S$ into two sets 'A'$A$ and 'B'$B$ and for both of these sets find vertices $x_A$ and $x_B$ from T$T$ such that the sum total of the distance between $x_A$ and the vertices of A$A$ and $x_B$ and the vertices of B$B$ should be a minimum.

How to approach this question?

Given that we know the distance relation for every pair of vertex, is it possible to know the minimum distance through some simple calculation?

Clustering of vertices in an n dimensional cube

Consider the vertices of an n-dimensional cube. Distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call the total set of vertices as 'T' and the subset as 'S' then our objective is to partition 'S' into two sets 'A' and 'B' and for both of these sets find vertices $x_A$ and $x_B$ from T such that the sum total of the distance between $x_A$ and the vertices of A and $x_B$ and the vertices of B should be a minimum.

How to approach this question?

Given that we know the distance relation for every pair of vertex, is it possible to know the minimum distance through some simple calculation?

Clustering of vertices in an $n$-dimensional cube

Consider the vertices of an $n$-dimensional cube. The distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call the total set of vertices as $T$ and the subset as $S$ then our purpose is to partition $S$ into two sets $A$ and $B$ and for both of these sets find vertices $x_A$ and $x_B$ from $T$ such that the sum total of the distance between $x_A$ and the vertices of $A$ and $x_B$ and the vertices of $B$ should be a minimum.

How to approach this question?

Given that we know the distance relation for every pair of vertex, is it possible to know the minimum distance through some simple calculation?

Bumped by Community user
Source Link
Vaisakh M
Vaisakh M
  • 41
  • 2

Clustering of vertices in an n dimensional cube

Consider the vertices of an n-dimensional cube. Distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call the total set of vertices as 'T' and the subset as 'S' then our objective is to partition 'S' into two sets 'A' and 'B' and for both of these sets find vertices $x_A$ and $x_B$ from T such that the sum total of the distance between $x_A$ and the vertices of A and $x_B$ and the vertices of B should be a minimum.

How to approach this question?

Given that we know the distance relation for every pair of vertex, is it possible to know the minimum distance through some simple calculation?