arXiv:1706.03065v1 [] 9 Jun 2017

Towards balanced clustering - part 1 (preliminaries)
Mark Sh. Levin

∗

The article contains a preliminary glance at balanced clustering problems. Basic balanced structures
and combinatorial balanced problems are briefly described. A special attention is targeted to various
balance/unbalance indices (including some new versions of the indices): by cluster cardinality, by cluster
weights, by inter-cluster edge/arc weights, by cluster element structure (for element multi-type clustering). Further, versions of optimization clustering problems are suggested (including multicriteria problem
formulations). Illustrative numerical examples describe calculation of balance indices and element multitype balance clustering problems (including example for design of student teams).
Keywords: balanced clustering, combinatorial optimization, heuristics, applications

Contents
1 Introduction

1

2 Basic balanced structures

4

3 Combinatorial balancing problems

6

4 Balance/unbalance indices for clustering solution

7

5 Optimization problem formulations for balanced clustering

9

6 Illustrative examples
6.1 Illustration example for description of cluster structure . . . . . . . . . . . . . . . . . . . .
6.2 Network-like illustration example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Cluster structure based balanced clustering for student teams . . . . . . . . . . . . . . . .

10
10
10
13

7 Conclusion

15

8 Acknowledgments

15

1. Introduction
Balancing processes play central roles in many theoretical and practical fields (Fig. 1) [9,10,12,31,35,
36,40,54,56,61,91,93,110,120,129,134,139,150]. The corresponding balancing problems are basic ones in
various engineering domains, for example: manufacturing systems, computing systems, power/electricity
systems, radio engineering systems, communication systems, and civil engineering systems. Similar balancing problems are examined in engineering management (e.g., coordination science), communications
(e.g., synchronization as time-based balancing), organization science, psychology. In recent decades, the
balancing approaches are very significant from the viewpoint of system modularity [16,65,86,103,112].
∗ Mark

Sh. Levin: Inst. for Inform. Transmission Problems, Russian Academy of Sciences; http://www.mslevin.iitp.ru;
email: mslevin@acm.org

2
✬
Initial data:
(a) element set, element
attributes;
(b) element set with
structure over the set
✫
Fig. 1. Scheme

✩

Balanced
structure
✏
✏
✓
✓
✎ ☞
✎ ☞
✛
✲
Solving
✍ ✌
✍ ✌
✒
✑
✒
✑
=⇒ (process of =⇒ ✻ ❅
■✒ ✻
✏
✏
✓
✎❄ ✠
☞
✎❄ ☞
❘✓
❅
balancing)
✛
✲
✍ ✌
✍ ✌
✒
✑
✒
✑
✪
of balancing process

The basic balancing problem consists in partitioning the element set (while taking into account element
parameters, structure over the elements) into interconnected element groups (clusters) which are balanced
(by cardinality of cluster elements, weight of cluster as a total weight of cluster elements, weight of
cluster interconnections, structure of cluster, etc.). A general framework of balancing problems domain
is depicted in Fig. 2.
✟
✙
✟
Balanced structures:
balanced set partition,
balanced cluster set,
✲
balanced tree, balanced ✛
graph partition,
balanced sign graph,
balanced matrix, etc.

❍
❥
❍
Solving methods:
Balancing
problems/models:
exact algorithms,
balance partition, ✛
✲ approximation
load balancing,
algorithms,
assembly line
heuristics,
balancing, etc.
metaheuristics

✻
✻
✻
❄
❄
❄
Applications (applied systems: manufacturing, computing,
communications, transportation, etc.)
Fig. 2. General framework of balancing problems domains
It is reasonable to point out the following main application domains with using the balanced structures:
1. hierarchical organization of storage and search processes in information systems and in computer
systems (e.g., various balanced search trees BSTs: AVL trees, red-black trees, splay trees) [2,13,88,93,
103,106,143];
2. balanced parallel scheduling of computing processes (e.g., computing in multi-processor systems,
distributed computing) [12,31,145];
3. service partitioning in a grid environment [119,120];
4. balanced partitioning in networks (e.g., modularization), balanced allocation of centers in networks
[18,54];
5. balanced partitioning of algorithms [139];
6. balanced manufacturing scheduling in manufacturing systems (e.g., assembly line balancing problems) [6,9,35,36,61,62,64,80];
7. design of balanced hierarchical structures in organizations [10,129];
8. design and management in communication systems (network design, routing, etc.) based on balanced
hierarchical structures [91,110]; and
9. design of distributed defence systems [74,150].
Evidently, balanced clustering problems (including combinatorial clustering, constrained clustering,
etc.) are used as the basic balancing combinatorial models for all domains [19,34,104,105]. Some basic
balanced clustering problems are pointed out in Table 1.
In general, the clustering problem is the following. Let A = {a1 , ..., aj , ..., an } be the initial set of
elements (items, objects). Usually, the following characteristics are examined:
(1) parameters of each element aj ∈ A as vector p(aj ) = (p1 (aj ), ..., pi (aj ), ..., pm (aj ));
(2) structure(s) (binary relation(s)) over the elements set A: G = (A, E) where E is a set of edges/arcs
(or weighted edges/arcs).
A clustering solution consists of a set of clusters (e.g., without intersections) [104,105]:
e = {X1 , ..., Xι , ..., Xλ },
X

3
i.e., dividing the set A into clusters: Xι ⊆ A ∀ι = 1, λ, ηι = |Xι | is the cluster size (cardinality of cluster
Xι , ι ∈ 1, λ ).
No.
1.
2.

Table 1. Basic balanced clustering problems
Basic types of initial data
Results
Set of elements, element
Set of balanced clusters
parameters
Set of elements with relations:

2.1.

Set of elements with precedence
relation

2.2.

Set of elements with various
binary relation(s)
(e.g., precedence, inclusion)

3.

Set of element chains
(trajectories)

4.

Set of element structures (e.g.,
programs, data structures, groups
of technological operations, teams)

(1) chain over balanced clusters
(balanced one-processor scheduling)
(2) parallel balanced element groups
(precedence over elements in each
group, multiprocessor scheduling)
(1) Tree/forest/hierachy over
balanced clusters (search structure,
hierarchical storage paging,
balanced broadcasting)
(2) k-layer network architecture
(hierarchical communications,
hierarchical distributed computing)
Special time interval balanced
scheduling of element chains
(scheduling in homebuilding)
Set of balanced clusters of element
structures (e.g., distributed
computing, technological plans)

Some source(s)
[19,34,97,104,107]
[111,140,141,154]
[1,14,44,51,77,98]
[102,103,123,128]
[142,151,152,154]

[35]

[104,106]

The basic balance (or unbalance/mismatch) index (parameter) for clustering solution is the difference
between the maximal cardinality of a cluster and minimal cardinality of a cluster (in the considered
clustering solution):
e = max ηι − min ηι .
B c (X)
ι=1,λ

ι=1,λ

Thus, the balanced clustering problem is targeted to search for the clustering solution with minimum
balance index (e.g., index above). Clearly, additions to the balanced problem statement can involve the
following: (a) some constraints: the fixed number of clusters, restriction(s) to cluster sizes (including
specified integer interval), etc.; (b) objective function(s) (e.g., minimization of total interconnections
weight between clusters, maximization of total element connections weight in clusters).
This material contains an author preliminary outline of balanced clustering problems. The basic balanced structures are pointed out. New balance/unbalance indices for clustering solutions are suggested.
Formulations of balanced optimization problems are described (including multicriteria problem formulations). Several numerical examples illustrate calculation of balance/unbalance indices for clustering
solutions. A special example for design of student teams (as element multi-type cluster structure balanced clustering problem) is described. The material can be considered as a continuation of the author
preprint on combinatorial clustering [104] and the corresponding article [105].

4
2. Basic balanced structures
The following basic balanced structures can be pointed out:
1. Balanced set partition (by cardinality, by element weights, element structure; in the general case,
the obtained subsets can have intersections): (a) a basic illustration (Fig. 3), (b) balancing by element
structure in each subset (Fig. 4).
2. Chain of balanced clusters (balanced manufacturing line, balanced chain of computing tasks groups,
etc.) (Fig. 5).
3. Balanced packing of bins (e.g., multi-processor scheduling) (Fig. 6).
4. Balanced β-layer clustering (i.e., partitioning the initial element set into clusters and layers; e.g., to
obtain a two-layer hierarchy with balances at the layer of clusters and at the layer of cluster groups, this
is a two-balancing case) (Fig. 7).
5. Balanced trees [3,49,93]: 5.1. balanced trees: by height (Fig. 8), by degree (Fig. 9),
5.2. balanced search trees (as search index structures): (a) AVL trees, self-balancing (or height balancing) binary search tree [2], (b) B-trees (path length from the root to each leaf equals b or b + 1 (where
b is a constant) (Fig. 8) [20,49,93], (c) Red-Black trees (symmetric binary B-tree) [21,49], etc.
6. Balanced graph partition (e.g., partition of a graph into balanced subgraphs/communities while
taking into account vertex weights or/and edge weights) (Fig. 10).
7. k-optimal partition of directed graph (path partition) [22,26,27] (Fig. 11).
8. Balanced signed graph [4,75,79,133,134] (Fig. 12).
9. Multi-layer structure of balanced clusters in networking: 9.1 hierarchy over balanced clusters
(networking) (Fig. 13); 9.2 balanced clustering based multi-layer network structure (Fig. 14).
10. Balanced matrices [25,47,131].
Balanced subsets (by
(cardinalities, by element
weights, by element structures)
✏
★✥
✓
✓✏
✓ ✏
✶
✏
✏
✒
✑
Initial
✲✛
✒✑
✘
✒ ✘
✑
element
✛
set P
q
P
✚ ✙
✧✦
✚✙
Fig. 3. Balanced set partition

Cluster
Cluster X3 ✘
Cluster
✛ X1✘
✛ X2✘
✛
r❡ s
r❡ s
r❡ s
❜ ❜ ❜
❜ ❜ ❜
❜ ❜ ❜ ❜
✚
✙
✚
✙
✚
✙

Cluster X4✘
Cluster
Cluster X6 ✘
Cluster X7 ✘
✛
✛ X5✘
✛
✛
r❡ s
r❡ s
r❡ r❡ s
r❡ s s
❜ ❜ ❜
❜
❜
❜ ❜ ❜ ❜
❜ ❜ ❜ ❜
✚
✙
✚ ✙
✚
✙
✚
✙
Fig. 4. Balanced cluster set (by subset structures)
Multi-bin (multi-container,
multi-processor, multi-knapsack)
system
✬ ✩
✎
☞
✲
✈ t ✇ s ✉
Bin 1
✲ ✍
Initial
✌
✎
☞
✲
set of
t s ✉ s t s
Bin 2
elements ✲ ✍
✌
...
(objects, ✲ ✎
☞
items)
✲
✉ t ✈ ✈
Bin k
✫ ✪
✍
✌
Fig. 6. Balanced packing of bins

Chain of clusters
✩
(balanced manufacturing line,
✲
balanced chain of
computing tasks groups)
Initial set ✲ ✎
✎ ☞
✎ ☞
✎ ☞
☞
of elements ✲
✍ ✌
✍ ✌
✍ ✌
(objects, ✲ ✍ ✌
items)
✲
✫ ✪
Fig. 5. Chain of balanced clusters
★✥
★
✥
✎ ☞
☛ ✟
Two-layer
✶
✏
✏
✍✟ ✌clustering
✡☛ ✠
✈
✟❍
Initial
✡
✠✬
✧
✦
✩
✲✬
✩
✟✟ ❍❍
☛
✟
✟
✟
☛
☛
element
✟
❍✉
❍
✟✉
❍
✟
set
✡
✠
✡
✠
❍❍s
✟
✡
✠
✎ ☞☛ ✟
✎
☞
☛
✟
s
s
s
s
✟
P
q
P
❍
❍
❅
❅
❅
✡ ✠
✍ ✌✡ ✠
q❝ q❝ ❝q
q❝ ❅q❝ q❝ q❝ q❝ ❅q❝ q❝ ❅❍
q❝ ❍q❝
✍
✌
✧✦
✫
✪
✫
✪
Fig. 7. Balanced two-layer clustering
Fig. 8. Height-balanced tree

✬

5

q❝

✟✇
✟
❅
✟
✟
✉
q❝ ❅✉
❅
❅
s q❝ ❅q❝ q❝ s ❅q❝
❅
❅
q❝ ❅q❝
q❝ q❝ ❅q❝

Fig. 9. 3-degree tree

′
Cluster X ′
Cluster
3
★X✥
✬ 2✩
q❝❢2
1 q❝❢
✁❆
✁❆
′
4
✁ ❆4
✁ ❆ Cluster
★X✥
6
❆r
r❞✁5 ❆r❞
r7
3 r✁
❆
✁
✁❆
✫ ◗✪
◗
✬ ✩
◗ ❆ ✁ 11✁ ❆
9 q❝❢
◗
◗
❆r✁10 ✦
✁q❝❢ 12❆q❝❢
❞
r
8
✧
◗
✁
❅
◗ ❆
◗❆ ✁
❅
13r
◗
◗❆✁r❞
❅r❞
15 ✦
14 Cluster
✧
✫
✪
X1′
Fig. 10. Graph partitioning

→
−
✩
✬ G = (A, E )
µp−1 µp
µ2
r❡
q❞ s✛ s
µ1
✻ ... ❅
■
r❡
r
❅q❞ ✻
s
✻
✻ ...
✻
r❡
r
s
q❞ ✻
✻
✻
✻
✻
r❡
r
q❞ s
✫
✪
Fig. 11. k-optimal partition of digraph

r❡
r
❡
t
“+”
❅
❅
❅
❅ “-”
“+”
“-” “+” “-”
❅ “+”
“-” ❅“-”
❅
❅
r “-” t “+” ❅t “-” ❡
❡
r “-” ❅t
Fig. 12. Balanced sign graph

Ordinary
Base station/ Cluster ✎ ☞
nodes
heads
☞
✎
❍
mobile observer
✑
❥t
❍
✰
q✑
✟
✟
t
q
❏
✍ ✌
❍
❍q ✌
✬ ✩
✍
✎ ☞
✎q ☞
✎ ☞
✲ ❏
❄
Initial set
❫
✟q
t
t
t✟
✲ ❏
✟
❍
✐ ✟✍
r❢
❍q
of elements
✌
✍
✌
✍
✎q ☞ ✌
✟ ✎ ☞
(objects, ✲
❍
✟q
t✟
✁❆ ❍❍ t✟
✎q ☞
✟ ❍
❍q ✌
items, end- ✲ ✁ ❆
✍
❍
✟q
✲
t✟
❍
✍
✌
users)
❍
❍q ✌
✫ ✪
✍
Fig. 13. Hierarchy over balanced clusters (network)
Domain 1 (Up-layer)
✩
r ✲r
✘
✿
✘
❍
✬ ✩
❥
❍
✘
✲
r
✲
q
r
❳❳❳
✘✘
❍❍
③ ❝q
✲
q❞
✘
PP
❥
❍
r
❳
P
Initial set ✲
❳❳
✻
P
q q❝
P
③ ❝q
✫
✪
of elements ✲
(objects, ✲
Domain 3 ✘
4
Domain
Domain 2 ✘ ✛
Domain 5
✘
✘
✛
✛
items)
g
✲✛
❄
h
s
❝q ✲ r ✲ r
31
g
g
✿
✘
0 r
✫ ✪
✘
g
❄
❄
✲
✲
h✟
✘
❝
q
❝
q
s
r
h
h
❳❳❳
41✘✘
❅
✯❍
❥ r✲ q❝
❍
❍
s✟
❘s ❄
❅
❥ s42
❍
③ s g h32
✾
s✘
shg53
hg51 s✠hg52
✚
✙ ✚ h33
✙
✚
✙
✚
✙
Fig. 14. Balanced clustering based multi-layer network structure
✬

6
3. Combinatorial balancing problems
A list of basic balancing combinatorial optimization problems is presented in Table 2.
No.
I.
1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
1.7.
1.8.
1.9.
1.10.
1.11.
1.12.
1.13.
1.14.
1.15.
1.16.
1.17.
II.
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.7.1.
2.7.2.
2.7.3.
2.7.4.
2.7.5.
2.7.6.
2.8.
2.9.
2.10.
2.11.
2.12.

Table 2. Basic balancing combinatorial (optimization) problems
Combinatorial problem
Some sources
Balanced partitioning problems:
Balanced partition problems (partition of set into balanced subsets) [75,82,94,115]
k-balanced partitioning problem (partition of set into k balanced
[69,73]
subsets)
Partitioning (hierarchically clustered) complex networks
[104,116]
via size-constrained graph clustering
Uniform k-partition problem
[58]
Quadratic cost partition problem
[76]
Multi-constraint partitioning problem
[81]
Tree-balancing problems
[2,13,88,93,143]
Minimum graph bisection problem
[75,83]
Simple graph partitioning problem
[75,144]
Balanced graph partitioning (partition of graph into balanced
[8,12,23,28,38]
components)
[66,72,95,113]
Balanced partitioning of trees
[71,100,103]
Balanced partitioning of grids and related graphs
[68]
Directed acyclic graph (DAG) partition
[29,99]
Graph-clique partitioning problem
[30,32,43,63,75]
[85,92,126,127,132]
Multiply balanced k-partitioning of graphs
[7]
Partitioning a sequence into clusters
[89]
with restrictions on their cardinalities
General partition data model
[117]
Some basic balanced combinatorial optimization problems:
Balanced knapsack problems, knapsack load balancing
[15,75,114]
Balanced bin packing, container loading
[55,57,75]
Balanced parallel processor scheduling, balanced job scheduling
[42,48,75,135,145]
in grids
Balanced allocation
[11,24,53,90]
Balanced k-center problem, balanced k-weighted center problem
[18,70,108]
Matrix balancing
[17,41,118,137,153]
Load balancing problems in distributed systems:
Load balancing in computer systems, in multiple processor
[45,46,52,106,109]
systems
[121]
Load balancing in telecommunications networks
[138]
Load balancing in structuring P2P systems
[130]
Load balancing in web-server systems
[39]
Load balancing in sensor networks
[84]
Special partition of multi-hop wireless network
[78]
(via graph coloring) for scheduling
Assembly line balancing problems
[5,9,36,37]
[80,136]
Balanced graph matching
[50]
Route balancing problems
[87,96,122,124,125]
Partition and balancing in meshes
[59,60,146,147,148]
Balanced combinatorial cooperative games
[67]

7
4. Balance/unbalance indices for clustering solution
e = {X1 , ..., Xι , ..., Xλ }. Let
Here, balance/unbalance indices are described for clustering solution X
p (Xι ) be a total parameter for cluster Xι (ι = 1, λ) (e.g, the number of elements, total weight). In
e can be defined via two methods:
general, a balance/unbalance index for clustering solution X
bal

Method 1: The balance (unbalance) index is defined as the following:
e = max pbal (Xι ) − min pbal (Xι ).
B(X)
ι=1,λ

ι=1,λ

Note, assessment of pbal (Xι ) can be based on various scales: quantitative, ordinal, poset-like (e.g.,
multiset-based) [101,103]. Now, the following additional element parameters are considered:
1. The weight of item w(aj ) ∀aj ∈ A (e.g., w(aj ≥ 0).
2. The weight of edge/arc between items v(aj1 , aj2 ) ∀aj1 , aj2 ∈ A, (aj1 , aj2 ) ∈ E (e.g., v(aj1 , aj2 ) ≥ 0).
3. The structure of cluster by elements types is defined as a special multiset estimate [101,103]:
e(Xι ), ι = 1, λ, e(Xι ) = (θ1 , ..., θγ , ..., θγ ), where θγ equals the number of element of type γ ( γ = 1, γ )
Pγ
in cluster Xι , the set of element types is: {1, ..., γ, ..., γ},
γ=1 θγ = |Xι |. In Fig. 4, an example with
e = {X1 , X2 , X3 , X4 , X5 , X6 , X7 }).
three element types is depicted (clustering solution X
In addition, a special “empty” element type is considered with the number γ + 1. This is a basis to
consider the clusters of the same size (cardinality) to compare their structure:
for each cluster multiset estimate the following element is added: θγ+1 , for cluster of the maximal size
θγ+1 = 0, otherwise θγ+1 = |X|max − |Xι |, where |X|max is the maximal cluster size.
As a result, the number of components in each multiset estimate of cluster structure will be the same.
The proximity between structure estimates for two clusters will be examined as a way (the number of
steps) from one estimate to another estimate [101,103] (this is a simplified definition of the multiset
estimate proximity). Note, the element types are linear ordered by importance/complexity (example for
four types) 1  2  3  4. The ordering can be considered as a complexity of communication node, for
example: access point (1), transition node (2), end-node (3), “empty” element (4). Thus, corresponding
lattice based scale can be used [101,103].
As a result, the following balance indices for clustering solution can be examined (for method 1):
(1.1) balance index by cluster cardinality is:
e = max |Xι | − min |Xι |.
B c (X)
ι=1,λ

ι=1,λ

(1.2) balance index by total cluster weight:
X
X
e = max
B w (X)
w(aj ) − min
w(aj ).
ι=1,λ a ∈X
j
ι

ι=1,λ a ∈X
j
ι

(1.3) balance index by total inter-cluster edge/arc weight:
X
X
e = max
v(aj1 , aj2 ) − min
v(aj1 , aj2 ).
B v (X)
ι=1,λ a ,a ∈X
ι
j2
j1

ι=1,λ a ,a ∈X
ι
j2
j1

(1.4) balance index by total cluster structure:
e = max e(Xι ) − min e(Xι ).
B s (X)
ι=1,λ

ι=1,λ

Method 2. Here, the balance/unbalance index is defined as the following:
b X)
e = max |pbal (Xι ) − p0 ,
B(
ι=1,λ

where p0 is a special specified (e.g., average) parameter of a special reference (e.g., average) cluster
X 0 (size, weight, interconnection weight, structure estimate). Thus, the following balance indices for
clustering solution can be examined:

8
(2.1) balance index by cluster cardinality is:
b c (X)
e = max | |Xι | − p|X 0 | |,
B
ι=1,λ

where p|X 0 | is a special specified (e.g., average) cluster size.
(2.2) balance index by total cluster weight:
X
b w (X)
e = max |
B
w(aj ) − pw0 |,
ι=1,λ

aj ∈Xι

where pw0 is a special specified (e.g., average) cluster weight.
(2.3) balance index by total inter-cluster edge/arc weight:
X
b v (X)
e = max |
v(aj1 , aj2 ) − pv0 |,
B
ι=1,λ

aj1 ,aj2 ∈Xι

where pv0 is a special specified (e.g., average) cluster weight of inter-cluster interconnections (i.e., edges/arcs).
(2.4) balance index by total cluster structure:
b s (X)
e = max | e(Xι ) − ep0 |,
B
ι=1,λ

where ep0 is a special specified (e.g., average) multiset estimate of cluster structure.
Table 3 contains the list of the considered balance indices. Note, a hybrid balancing (i.e., by several
balance parameters) can be examined as well.

No.
I.
1.1.
1.2.
1.3.
1.4.
II.
2.1.
2.2.
2.3.
2.4.

e
Table 3. Balance/unbalance indices of clustering solution X
Description
Method 1 (difference between maximal and
minimal values of cluster total parameters):
Balance index by cluster cardinality
Balance index by total cluster weight
Balance index by total inter-cluster edge/arc weight
Balance index by cluster element structure
Method 2 (maximal difference between cluster total parameters
and special reference specified (fixed) cluster total parameter):
Balance index by cluster cardinality
Balance index by total cluster weight
Balance index by total inter-cluster edge/arc weight
Balance index by cluster element structure

Notation

e
B c (X)
w e
B (X)
e
B v (X)
s e
B (X)
b c (X)
e
B
w e
b
B (X)
b v (X)
e
B
s e
b
B (X)

9
5. Optimization problem formulations for balanced clustering
Thus, the balanced clustering problem is targeted to search for the clustering solution with minimum
balance index (e.g., index above). Clearly, additions to the balanced problem statement can involve the
following: (a) some constraints: the fixed number of clusters, restriction(s) to cluster sizes (including
specified integer interval), etc.; (b) objective function(s) (e.g., minimization of total interconnections
weight between clusters, maximization of total element connections weight in clusters).
The described balanced indices for clustering solutions can be used as objective functions and a basis
for constraints in formulations of optimization balanced clustering models, for example:
Problem 1:
e
min B c (X)

e ≤ w0 , B s (X)
e  e0 ,
s.t. B w (X)

where w0 is a constraint for cluster weight difference, e0 is a constraint for cluster structure difference.
Problem 2:
e
min B w (X)

e ≤ c0 , B s (X)
e  e0 ,
s.t. B c (X)

where c0 is a constraint for cluster cardinality difference, e0 is a constraint for cluster structure difference.
Problem 3:
e
min B w (X)

e ≤ c0 , |X|
e ≤ λ0 ,
s.t. B c (X)

where c0 is a constraint for cluster cardinality difference, λ0 is a constraint for numbers of clusters in the
clustering solution.
Evidently, multicriteria optimization models can be examined as well, for example:
Problem 4:
e c (X),
e
e v (X)
e
min B
min B

e ≤ w0 , B
e s (X)
e  ee0 ,
s.t. B w (X)

where w0 is a constraint for cluster weight difference, ee0 is a constraint for cluster structure difference
based on a reference value.
Problem 5:
e c (X),
e
e w (X),
e
e v (X)
e
min B
min B
min B

e s (X)
e e
e ≤ λ0 ,
s.t. B
e0 , |X|

where ee0 is a constraint for cluster structure difference based on a reference value, λ0 is a constraint for
numbers of clusters in the clustering solution.
Problem 6:
e
min B w (X),

e v (X)
e
min B

e ≤ c0 , B
e s (X)
e  ee0 ,
s.t. B c (X)

where c0 is a constraint for cluster cardinality difference, ee0 is a constraint for cluster structure difference
based on a reference value.

10
6. Illustrative examples
6.1. Illustration example for description of cluster structure
Table 4 contains a description of cluster structures and corresponding multiset estimates for example from Fig. 4 (seven clusters, tree types of elements and additional “empty” element type).
Table 5 contains the simplified proximity (or distance) between the multiset estimates of the clusters: δ(e(Xι1 ), e(Xι2 )), ι1 , ι2 ∈ {1, ..., 7}.

Cluster Xι
X1
X2
X3
X4
X5
X6
X7

Table 4. Cluster structures for example from Fig. 4
Element type: θ1 θ2 θ3 θ4 (“empty” element) Multiset estimate e(Xι )
1
1
3
2
(1, 1, 3, 2)
1
1
3
2
(1, 1, 3, 2)
1
1
4
1
(1, 1, 4, 1)
1
1
3
2
(1, 1, 3, 2)
1
1
2
3
(1, 1, 2, 3)
2
1
4
0
(2, 1, 4, 0)
1
2
4
0
(1, 2, 4, 0)

Table 5. Proximity for cluster structures (example from Fig. 4):
Cluster Xι1 Cluster Xι2 : X1 X2 X3 X4 X5
X1
0
0
1
0
1
X2
0
0
1
0
1
X3
1
1
0
1
2
X4
0
0
1
0
1
X5
1
1
1
1
0
X6
4
4
3
4
5
X7
3
3
2
3
4

δ(e(Xι1 ), e(Xι2 ))
X6 X7
4
3
4
3
3
2
4
3
5
4
0
1
1
0

For clustering solution from Fig. 4, the following balance indices are obtained:
e = 7 − 4 = 3, B s (X)
e = e(X6 ) − e(X5 ) = (2, 1, 4, 0) − (1, 1, 2, 3) = δ(e(X6 ), e(X5 )) = 5.
B c (X)
Further, cluster X1 is considered as a reference cluster with corresponding its parameters. As a result,
the following balance indices are obtained:
b c (X)
e = |X6 | − |X1 | = 2, B
b s (X)
e = δ(e(X6 ), e(X1 )) = δ((2, 1, 4, 0), (1, 1, 3, 2)) = 4.
B
6.2. Network-like illustration example
In general, a wireless sensor network (WSN) can be considered as a multi-layer system (Fig. 15)
[33,149]: (1) sensors, (2) clusters, (3) cluster heads, (4) sink, (5) database server, and (6) decision/control
center. The design process of the architecture is based on element multi-type clustering (i.e., sensor/end
nodes, cluster heads, etc).
✟
❍
✟
❍❍Analysis/decision/control center✟❍
✟
❅
✠
❘
❅
✻
Control
Control
action
action
Database server
✻
✲ Sink

✟
✟✟
Cluster heads
PP
✟
✚
r❡✛
✟
✐
P
✶ r❡
✏
PP
✏
✚
✬
P✩
✏✏
✚ ✏✏
r❡
✛
PP
❨❍
✯ ❍
✟
r❳
r
✚ ✏
PP ✚
✘✘
❳❳
■ ❍s
❅
✾
✘
③ r❡✛
s✟✟
s✒ ✻
r❡ ✏
P✏
✿
②
❳
✟✟ r✘✘✘
❅
❳❳rr
Cluster 2 Sensors ✚
s ❅s ✛
✘
❩
❩
r ❳
r
✘
❳
Cluster 3
✫
✪
✘
③
❳
✾
✲
r ✘
②❳❳r
❳
✿ r❡✘
Cluster 1
r✘ ✘
✚
✙
Fig. 15. Multi-layer architecture of WSN

✘

✙

11
Here, a numerical example from Fig. 10 is considered (three types of elements: ordinary nodes, nodes
for relay, cluster heads): A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. Parameters of elements and their
interconnection are presented in Table 6 (element weights, element types) and Table 7 (weights of edges,
e ′ = {X ′ , X ′ , X ′ , X ′ }
symmetric weighted binary relation). The considered four-cluster solution is: X
1
2
3
4
′
′
′
′
where X1 = {8, 9, 13, 14}. X2 = {1, 3, 4}, X3 = {2, 5, 6, 10}, and X4 = {7, 11, 12, 15}. Proximities
between cluster structures are presented in Table 8. Fig. 16 depicts the poset-like scale P 4,4 [101,103]
for cluster structure, where multiset estimate of the cluster structure is: e(Xι ) = (αθ1 , αθ2 , αθ3 , αθ4 ).
☛
✟
☛
✟
Maximum (4, 0, 0, 0)
point
✠
✡
✠
✟
☛
(3, 1, 0, 0) ✠
✡
PP
PP
P
☛
✟☛
✟
′
(3,
0,
1,
0)
(2,
2,
0,
0)
maxι e(Xι ) ✡
✠✡
✠
❳❳❳ P
P
PP
PP
❳❳
P
PP
❳✟
P
❳
③☛
❳
✟
☛
✟☛
(1, 3, 0, 0) ✠
(3, 0, 0, 1) ✠✡
(2, 1, 1, 0)✠✡
✡
❳
❳✏
❳✏
✏✏
❳❳❳
✏
✏
✏
✏ ✟☛
✏✏
❳✟
❳☛
☛
✟☛
✟
(2,
1,
0,
1)
(1,
2,
1,
0)
(0,
4,
0,
0)
(2,
0,
2,
0)
✡
✠✡
✠✡
✠✡
✠Reference
❳
P
P
PP
P❳
❳❳
structure
PP
❳
PP
P ❳❳✟
✠
❳☛
✟☛
✟☛
☛
✟ ep0
(2, 0, 1, 1) ✠✡
(1, 2, 0, 1) ✠✡
(0, 3, 1, 0) ✠✡
(1, 1, 2, 0)✠
✡
✘❳
❳
❳
✘
P
PP
✘
❳❳❳
✘
PP
✘✘
❳✟
✘
✘
❳☛
☛
✟☛
✟☛
✟☛
✟
(2,
0,
0,
2)
(1,
1,
1,
1)
(0,
2,
2,
0)
(1,
0,
3,
0)
(0,
3,
0,
1)
✡
✠✡
✠✡
✠✡
✠✡
✠
❳
❳
❳✏
✏✏ minι e(Xι′ )
✏
❳❳
✏
✏
❳❳❳
✏ ✟☛
✏✟
✏
✏
✟ ✟☛
✙
✟
☛
✟
☛
(0, 2, 1, 1) ✠
(1,
1,
0,
2)
(1,
0,
2,
1)
(0,
1,
3,
0)
✠✡
✡
✠✡
✠
✡
✘
✏✏
✏✏
✘✘✘
✘
✏
✏
✘
✏
✏
✏ ✟☛
✏✘
✘☛
✟
✟
✟
☛
☛
(1,
0,
1,
2)
(0,
1,
2,
1)
(0,
0,
4,
0)
(0,
2,
0,
2)
✡
✠✡
✠✡
✠
✠
✘✡
P
P
PP
PP
✘✘
✘
✘
PP
PP
✘
✘
✘
☛
✟☛
✟☛
✟
(1,
0,
0,
3)
(0,
1,
1,
2)
(0,
0,
3,
1)
✡
✠✡
✠✡
✠
✏
✏
✏
✏
✏✏
✏✏
✏
✏
✟☛
✟
☛
(0,
1,
0,
3)
(0,
0,
2,
2)
✡
✠✡
✠
✏✏
✏
✏✟
✏
☛
(0,
0,
1,
3) ✠
✡
✟
Minimum ☛
point
(0,
0,
0,
4)
✡
✠
Fig. 16. Poset-like scale P 4,4 for e(Xι′ ) = (αθ1 , αθ2 , αθ3 , αθ4 ) [101,103]

The resultant integrated parameters of the clusters are contained in Table 9.
e′ =
Finally, the following balance indices on the basis of method 1 are obtained (clustering solution X
′
′
′
′
c e′
w e′
v e′
s e′
{X1 , X2 , X3 , X4 }): B (X ) = 1, B (X ) = 6.7, B (X ) = 13.9, B (X ) = 4.
Further, the following reference specified parameters for clusters are considered: p|X 0 | = 4, pw0 = 12.0,
pv0 = 15.0.
The reference cluster structure is: ep0 = (1, 1, 2, 0). Thus, the balance indices based on method 2 are:
b c (X
e ′ ) = 1, B
b w (X
e ′ ) = 4.7, B
b v (X
e ′ ) = 7.3, B
b s (X
e ′ ) = 2.
B

12

Element aj
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15

aj1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

aj2 :

Table 6. Parameters of elements (example from Fig. 10)
Cluster number ι (Xι′ ) Element weight w(aj ) Element
2
4.2
3
5.1
2
1.1
2
2.0
3
3.1
3
3.2
4
1.0
1
3.4
1
5.0
3
0.9
4
4.5
4
4.8
1
0.8
1
3.4
4
3.7

type θ(aj )
1
1
3
3
2
2
3
2
1
3
1
1
3
2
2

Table 7. Interconnection edge weights for example from Fig. 10
2
3
4
5
6
7
8
9
10 11 12 13
4.1 2.1
4.4 4.5
4.1
1.5
2.1
1.5
3.0 2.9 0.7
4.4
3.6
3.0 1.0
4.5
3.6
0.8
2.5 3.2
3.0
4.0
2.9 3.0
4.0
1.6
3.1
0.7 1.0 0.8
1.6
5.0
2.5
5.0
6.2
3.2
6.2
3.1
3.2 6.0
5.0
3.3 4.3 4.2
1

Table 8. Proximity for cluster structures (example
Cluster Xι′1 Cluster Xι′2 : X1′
X1′
0
X2′
2
X3′
0
X4′
1

Cluster
X1′
X2′
X3′
X4′

14

15

3.2
6.0
3.3
4.3
4.2
5.0
2.5
2.5

from Fig. 10): δ(e(Xι′1 ), e(Xι′2 ))
X2′ X3′ X4′
2
0
1
0
3
4
3
0
1
4
1
0

Table 9. Parameters
of clustersP
(example from Fig. 10)
P
ηι (Xι′ ) = |Xι′ |
aj ∈Xι′ w(aj )
aj1 ,aj2 ∈Xι′ v(aj1 , aj2 )
4
12.6
21.3
3
7.3
7.7
4
12.3
15.4
4
14.0
21.6

e(Xι′ )
(1, 2, 1, 0)
(1, 0, 2, 1)
(1, 2, 1, 0)
(2, 1, 1, 0)

e ′′ = {X ′′ , X ′′ , X ′′ , X ′′ } where X ′′ = {4, 8, 9, 13, 14}.
The second considered four-cluster solution is: X
1
2
3
4
1
′′
′′
= {1, 3}, X3 = {2, 5, 6}, and X4 = {7, 10, 11, 12, 15}.
Proximities between cluster structures are presented in Table 10. The resultant integrated parameters
of the clusters are contained in Table 11.
X2′′

13
e ′′ =
Finally, the following balance indices on the basis of method 1 are obtained (clustering solution X
e ′′ ) = 3, B w (X
e ′′ ) = 9.6, B v (X
e ′′ ) = 25.8, B s (X
e ′′ ) = 6.
{X1′′ , X2′′ , X3′′ , X4′′ }): B c (X
The basic reference specified parameters for clusters are considered as for previous clustering solution
e ′ ): p|X 0 | = 4, pw0 = 12.0, pv0 = 15.0.
(i.e., X
The reference cluster structure is: ep0 = (1, 1, 3, 0), Thus, the balance indices based on method 2 are:
b c (X
e ′′ ) = 2, B
b w (X
e ′′ ) = 6.7, B
b v (X
e ′′ ) = 11.9, B
b s (X
e ′′ ) = 4.
B
e ′ and X
e ′′ .
Table 12 contains the obtained balance indices for the considered clustering solutions X
Table 10. Proximity for cluster structures (example from
Cluster Xι′′1 Cluster Xι′′2 : X1′′ X2′′
X1′′
0
5
X2′′
5
0
X3′′
2
3
X4′′
1
6

Cluster
X1′′
X2′′
X3′′
X4′′

No.
I.
1.1.
1.2.
1.3.
1.4.
II.
2.1.
2.2.
2.3.
2.4.

Fig. 10): δ(e(Xι′′1 ), e(Xι′′2 ))
X3′′ X4′′
2
1
3
6
0
3
3
0

Table 11. Parameters
of clustersP
(example from Fig. 10)
P
ηι (Xι′′ ) = |Xι′′ |
w(a
)
j
aj ∈Xι′′
aj1 ,aj2 ∈Xι′′ v(aj1 , aj2 )
5
14.6
27.2
2
5.3
4.1
3
11.4
12.5
5
14.9
29.9

e(Xι′′ )
(1, 2, 2, 0)
(1, 0, 1, 3)
(1, 2, 0, 2)
(2, 1, 2, 0)

e ′ and X
e ′′
Table 12. Balance indices of clustering solutions X
e′
Description
Solution X
Method 1:
e ′) = 1
Balance index by cluster cardinality
B c (X
w e′
Balance index by total cluster weight
B (X ) = 6.7
e ′ ) = 13.9
Balance index by total inter-cluster edge/arc weight B v (X
s e′
Balance index by cluster element structure
B (X ) = 4
Method 2:
b c (X
e ′) = 1
Balance index by cluster cardinality
B
b w (X
e ′ ) = 4.7
Balance index by total cluster weight
B
v e′
b
Balance index by total inter-cluster edge/arc weight B (X ) = 7.3
b s (X
e ′) = 2
B
Balance index by cluster element structure

e ′′
Solution X
e ′′ ) = 3
B c (X
w e ′′
B (X ) = 9.6
e ′′ ) = 25.8
B v (X
s e ′′
B (X ) = 6
b c (X
e ′′ ) = 2
B
b w (X
e ′′ ) = 6.7
B
v e ′′
b
B (X ) = 11.9
b s (X
e ′′ ) = 4
B

6.3. Cluster structure based balanced clustering for student teams
The considered numerical example is a modification of an example from [104]. There is a set of
13 students A = {a1 , ..., aj , ..., a13 } (Table 13) in the field of radio engineering. Four inclination/skill
properties of the students are considered as parameters/criteria (student estimates are shown in Table
13): (i) inclination (skill) for mathematics C1 , (2) inclination (skill) for theoretical radio engineering C2 ,
(3) skill for technical works in radio engineering (usage of radio devices, design of scheme, analysis of
signals, etc.) C3 , (4) writing skill (e.g., to prepare a laboratory work report/paper) C4 . The following
scale is used: [0, 1, 2, 3], where 0 corresponds to absent inclination/skill), 1 corresponds to low level
of inclination/skill), 2 corresponds to medium level of inclination/skill), 3 corresponds to high level of
inclination/skill). As a result, each student j (j = 1, 13) has a vector (4 component) estimate ξ(aj ) =
(ξ 1 (aj ), ξ 2 (aj ), ξ 3 (aj ), ξ 4 (aj )). It is assumed, each student has as minimum one “positive” inclination/skill
estimate (or more).
A symmetric weighted binary relation of student friendship Rf = {ε(aj1 , aj2 )} (j1 , j2 = 1, 13) (ordinal
scale [0, 1, 2, 3], 0 corresponds to incompatibility) is contained in Table 14.
Some notations are as follows. The structure of cluster is Xι = {b1 , ..., bτ , ..., bµι }.
Then the following cluster characteristics are examined:
1. The total vector estimate of the cluster structure is:
ξ(Xι ) = (ξ 1 (Xι ), ξ 2 (Xι ), ξ 3 (Xι ), ξ 4 (Xι )),

14
where ξ κ (Xι ) = maxτ =1,µι ξ κ (bτ ), ∀κ = 1, 4 (index of criteria/parameter).
2. The total
P estimate of the cluster by quality of intercluster compatibility is:
ε(Xι ) = bτ ,bτ ∈Xι ,bτ <bτ ε(bτ1 , bτ2 ).
1

2

1

2

Table 13. Items/students, estimates upon criteria
Item (student)
C1
C2
C3
C4
Vector estimate
aj
(ξ 1 (aj )) (ξ 2 (aj )) (ξ 3 (aj )) (ξ 4 (aj ))
ξ(aj )
Student 1 (a1 )
1
2
3
3
(1,2,3,3)
Student 2 (a2 )
0
1
2
1
(0,1,2,1)
Student 3 (a3 )
2
3
3
2
(1,3,3,2)
Student 4 (a4 )
2
2
1
3
(3,2,1,3)
Student 5 (a5 )
0
1
2
1
(0,1,2,1)
Student 6 (a6 )
3
3
3
3
(3,3,3,3)
Student 7 (a7 )
0
1
1
1
(0,1,1,1)
Student 8 (a8 )
0
2
2
2
(0,2,2,2)
Student 9 (a9 )
3
3
3
3
(3,3,3,3)
Student 10 (a10 )
3
3
2
3
(3,3,2,3)
Student 11 (a11 )
0
1
3
2
(0,1,3,2)
Student 12 (a12 )
0
2
3
1
(0,2,3,1)
Student 13 (a13 )
0
1
1
1
(0,1,1,1)
Table 14. Ordinal estimates of
aj1 / aj2 a2 a3 a4
a1
2
3
3
a2
2
3
a3
3
a4
a5
a6
a7
a8
a9
a10
a11
a12

student friendship (compatibility) Rf = {ε(aj1 , aj2 )}
a5 a6 a7 a8 a9 a10 a11 a12 a13
3
3
1
2
2
2
2
3
2
1
2
3
2
0
0
2
2
1
3
3
2
3
3
3
3
3
2
1
3
3
2
3
0
3
3
2
3
1
1
2
2
2
3
1
1
1
2
0
3
3
3
3
3
3
2
2
3
3
3
2
3
3
3
2
3
1
2
3
2
3
3
3

The clustering problem can be considered as the following:
e = {X1 , ..., Xι , ..., Xλ }) (i.e., a set of student teams as clusters/groups
Find the clustering solution X
without intersection) for implementation of special laboratory work(s) (e.g., in radio engineering) while
taking into account some requirements:
(a) constraints for the number of elements (students) in each cluster (i.e., cluster cardinality):
ηmin ≤ |Xι |;
(b) constraint for total inclination/skill in the cluster: ξ(Xι )  ξ0 = (2, 3, 3, 2);
e
(c) the objective function 1 is to minimize the balance index by cluster cardinality B c (X);
(d) the objective function 2 is to maximize (multicriteria case) the worst cluster structure estimate;
(e) the objective function 3 is to maximize the worst inter-cluster cluster estimate of element compatibility.
The version of the optimization problem for the example above can be considered as follows:
e = max |Xι | − min |Xι |,
min B c (X)
ι=1,λ

s.t.

ι=1,λ

3 ≤ |Xι | ≤ 4 ∀ι = 1, λ,

max min ξ(Xι ),
ι=1,λ

max min ε (Xι )
ι=1,λ

ξ(Xι )  ξ0 = (2, 2, 3, 2) ∀ι = 1, λ.

15
The combinatorial optimization models of this kind are very complicated (i.e., NP-hard). Thus, enumerative algorithms or heuristics (metaheuristics) are used.
Now, it is reasonable to describe a simplified heuristic (for the example above):
Stage 1. Counting an approximate number of clusters (e.g., 4).
Stage 2. Selection of the most important criteria: 1st choice: criterion 3, 2nd choice: criterion 2.
Stage 3. Selection of the best elements (about 4) from the viewpoints of the selected criteria (e.g., by
Pareto-rule) as kernels (“domain(s) leaders”) of the future clusters/teams. In general, small cliques or
quasi-cliques can be considered as the kernels. In the example, the elements are: a1 , a3 , a6 , a9 .
Stage 4. Extension of each kernel above by other elements while taking into account element compatibile = {X1 , X2 , X3 , X4 } (B c (X)
e = 1),
ity. As a result, the following clustering solution can be considered: X
where the clusters are:
(i) X1 = {a1 , a2 , a4 }, ξ(X1 ) = (2, 2, 3, 3), ε(X1 ) = 8;
(ii) X2 = {a3 , a7 , a8 }, ξ(X2 ) = (2, 3, 3, 2), ε(X2 ) = 8;
(iii) X3 = {a6 , a5 , a11 }, ξ(X3 ) = (3, 3, 3, 3), ε(X3 ) = 8;
(iv) X4 = {a9 , a10 , a12 , a13 }, ξ(X4 ) = (3, 3, 3, 3), ε(X4 ) = 15.
e = 7.
Note, balance index by total inter-cluster edge weight is B v (X)
e = {X1 , X2 , X3 , X4 } (edge weight/compatibility
Fig. 17 depicts the obtained four clusters solution X
estimates are pointed out).
Cluster X1
a2 s
✁❆
2✁ ❆ 3
✁
❆s a
a1 s❡
4
3

Cluster X2
a7 s
✁❆
2✁ ❆ 3
✁
❆s a
a3 s❡
8
3

Cluster X3
a5 s
✁❆
3✁ ❆ 2
a6 ✁s❡ 3 ❆sa11

Fig. 17. Clustering solution

X4
a10Cluster
s
sa12
◗
✑
◗ 3 ✑
◗✑ 2 3
3 3✑
◗
s❡
◗s
✑
a9
a13
1

7. Conclusion
The paper describes the author preliminary outline of various combinatorial balancing problems including new balance indices for clustering solutions, multicriteria combinatorial models and examples. It
may be reasonable to point out some prospective future research directions:
(1) special investigation of balance indices for balanced structures (degree of balance, etc.);
(2) study of various balancing problems in combinatorial optimization (e.g., balanced knapsack-like
problems, balanced allocation problems, balanced bin packing problems);
(3) taking into account uncertainty in the balancing models;
(4) examination of balancing clustering problems in networking (e.g., design of multi-layer communication networks, routing);
(5) study of augmentation approaches to balance structures while taking into account the improvement
of the structures balance; and
(6) usage of the described approaches in CS/engineering education.
8. Acknowledgments
The research was done in Institute for Information Transmission Problems of Russian Academy of
Sciences and supported by the Russian Science Foundation (grant 14-50-00150, “Digital technologies and
their applications”).
REFERENCES
1. A.A. Abbasi, M. Younis, A survey on clustering algorithms for wireless sensor networks. Comp.
Commun., 30(14-15), 2826–2841, 2007.
2. G.M. Adelson-Velsky, E.M. Landis, An algorithm for the organization of information. Soviet Math.
Doklady, 3, 1259–1263, 1962.

16
3. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and Algorithms. Addison-Wesley, Readings,
MA, 1983.
4. J. Akiyama, D. Avis, C. Chvatal, H. Era, Balancing sign graphs. Discr. Appl. Math., 3(4), 227–233,
1981.
5. M. Amen, Heuristic methods for cost-oriented assembly line balancing: a comparison on solution
quality and computing time. Int. J. of Prod. Res., 69, 255–264, 2001.
6. M. Amen, Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and
lower bounds. EJOR, 168(3), 747–770, 2006.
7. A. Amir, J. Ficler, R. Krauthgamer, L. Roditty, O.S. Shalom, Multiply balanced k-partitioning. In:
LATIN14, pp. 586–597, 2014.
8. K. Andreev, H. Racke, Balanced graph partitioning. Theory of Comput. Syst., 39(6), 929–939, 2006.
9. C. Andres, C. Miralles, R. Pastor, Balancing and scheduling tasks in assembly lines with sequencedependent setup times. EJOR, 187(3), 1212–1223, 2008.
10. N.S. Argyres, B.S. Silverman, R&D, organization structure, and the development of corporate technological knowledge. Strategic Management J., 25(8-9), 929–958, 2004.
11. Y. Azar, A.Z. Broder, A.R. Karlin, E. Upfal, Balanced allocations. SIAM J. on Computing, 29(1),
180–200, 1999.
12. D.A. Bader, H. Meyerhenke, P. Sanders, D. Wagner (eds), Graph Partitioning and Graph Clustering.
AMS, 2013.
13. J.-L. Baer, B. Schwab, A comparison of tree-balancing algorithms. Commun. of the ACM, 29(5),
322–330, 1977.
14. A. Balakrishnan, T. Magnanti, P. Mirchandani, A dual-based algorithm for multi-level network design.
Manag. Sci., 40(5), 567–581, 1994.
15. M.M. Baldi, G. Perboli, R. Tadei, The three-dimensional knapsack problem with load balancing.
Appl. Math. Comput., 218(19), 9802–9818, 2012.
16. C.Y. Baldwin, K.B. Clark, Design Rules: The Power of Modularity. MIT Press, Cambridge, Mass.,
2000.
17. M.L. Balinski, G. Demange, Algorithms for proportional matrices in reals and integers. Math. Programming, 45, 193–210, 1989.
18. J. Bar-Ilan, G. Kortsarz, D. Peleg, How to allocate network centers. J. of Algorithms, 15(3), 385–415,
1993.
19. S. Basu, I. Davidson, K. Wagstaff (eds), Constrained Clustering: Advances in Algorithms, Theory,
and Applications. CRC Press, 2008.
20. R. Bayer, E. McCreight, Organization and maintenance of large ordered indexes. Acta Informatica,
1(3), 173–189, 1972.
21. R. Bayer, Symmetric binary B-Trees: Data structure and maintenance algorithms. Acta Informatica,
1(4), 290–306, 1972.
22. I. Ben-Arroyo Hartman, Berge’s conjecture on directed path partitions - A survey. Discrete Math.,
306(19-20), 2498–2514, 2006.
23. U. Benlic, J.K. Hao, An effective multilevel tabu search approach for balanced graph partitioning.
Comp. and Oper. Res., 38(7), 1066–1075, 2011.
24. P. Berenbrink, A. Czumaj, A. Steger, B. Vocking, Balanced allocations: The heavily loaded case. In:
Proc. of the 32rd Annual ACM Symp. on Theory of Computing (STOC), pp. 745–754, 2000.
25. C. Berge, Balanced matrices. Mathematical Programming, 2(1), 19–31, 1972.
26. C. Berge, k-optimal partitions of a directed graph. Eur. J. Comb., 3(2), 97–101, 1982.
27. E. Berger, I. Ben-Arroyo Hartman, Proof of Berge’s strong path partition conjecture for k = 2. Eur.
J. of Combinatorics, 29(1), 179–192, 2008.
28. R. van Bevern, A.E. Feldmann, M. Sorge, O. Suchy, On the parameterized complexity of computing
balanced partitions in graphs. Theory of Comput. Syst., 57(1), 1–35, 2015.
29. R. van Bevern, R. Bredereck, M. Chopin, S. Hartung, F. Huffner, A. Nichterlein, O.
Suchy, Fixed-parameter algorithms for DAG partitioning. Electr. prepr., 33 p., Nov. 27, 2016.
http://arxiv.org/abs/1611.08809 []
30. J. Bhasker, The clique-partitioning problem. Computers & Math. with Appl., 22(6), 1–11, 1991.
31. C.-E. Bichot, P. Siarry (eds), Graph Partitioning, Wiley-ISTE, 2013.

17
32. K. Biswas, V. Muthekkumarasamy, E. Sithirasenan, Maximal clique based clustering scheme for
wireless sensor networks. In: 2013 Eight Int. Conf. on Intelligent Sensors, Sensor Networks and
Information Processing, pp. 237–241, 2013.
33. A. Bonivento, C. Fischione, L. Necchi, F. Pianegiani, A. Sangiovanni-Vincentelli, System level design
for clustered wireless sensor networks. IEEE Trans. Ind. Inf., 3(3), 202–214, 2007.
34. S. Borgwardt, S. Onn, Efficient solutions for weighted-balanced partitioning problems. Discr. Optim.,
21, 71–84, 2016.
35. P.A. Borisovsky, X. Delorme, A. Dolgui, Balancing reconfigurable machining lines via a set partitioning model. Int. J. of Prod. Res., 52(13), 4052–4036, 2014.
36. N. Boysen, M. Fliedner, A. Scholl, A classification of assembly line balancing problems. EJOR, 183(2),
674–693, 2007.
37. N. Boysen, M. Fliedner, A. Scholl, Assembly line balancing: Which model to use when. Int. J. of
Prod. Res., 111(2), 509–528, 2008.
38. A. Buluc, H. Meyerhenke, I. Safro, P. Sanders, C. Schulz, Recent advances in graph partitioning.
Electr. prepr., 37 p., Feb 3, 2015. http://arxiv.org/abs/1311.3144 []
39. V. Cardellini, M. Colajanni, S.Yu. Philip, Dynamic load balancing on web-server systems. IEEE
Internet Computing, 3(3), 28–39, 1999.
40. D. Cartwright, F. Harary, Structural balance: A generalization of Heider’s theory. Psychol. Rev., 63,
277–293, 1956.
41. Y. Censor, S.A. Zenios, Interval-constrained matrix balancing. Linear Algebra and Its Applications,
150, 393–421, 1991.
42. R.-S. Chang, J.-S. Chang, P.-S. Lin, An ant algorithm for balanced job scheduling in grids. Future
Generation Computer Systems, 25(1), 20–27, 2009.
43. I. Charon, O. Hudry, A branch and bound method for a clique partitioning problem. In: Extended
Abstracts of 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Cologne,
Germany, May 25-27, CTW 2010, pp. 43–46, 2010.
44. H. Cheng, S. Yang, Genetic algorithms with elitism-based immigrants for dynamic load balanced
clustering problem in mobile ad hoc networks. In: 2011 IEEE Symp. on Computational Intelligence
in Dynamic and Uncertain Environments (CIDUE), pp. 1–7, 2011.
45. T.C.K. Chou, J.A. Abraham, Load balancing in distributed systems. IEEE Trans. on Software Engrg.,
8(4), 401–412, 1982.
46. Y.C. Chow, W.H. Kohler, Models for dynamic load balancing in a heterogeneous multiple processor
system. IEEE Trans. on Comp., 28(5), 354–361, 1979.
47. M. Conforti, G. Cornuejols, K. Vuskovic, Balanced matrices. In: K. Aardal, G.L. Nemhauser, R.
Weismantel (eds), Handbooks in Operations Research and Management Science, Elsevier, vol. 12,
pp. 277–319, 2005.
48. R.W. Conway, W.L. Maxwell, L.W. Miller, Theory of Scheduling. Addison-Wesley, Readings, Mass.,
1967.
49. T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms. 3rd ed., MIT Press and
McGraw-Hill, 2009.
50. T. Cour, P. Srinivasan, J. Shi, Balanced graph matching. In: Neural Information Processing Systems
(NIPS), pp. 313–320, 2006.
51. J. Current, C. ReVelle, J. Cohon, The hierarchical network design problem. EJOR, 27(1), 57–66,
1986.
52. G. Cybenko, Dynamic load balancing for distributed memory multiprocessors. Paral. Distr. Comput.,
7, 279–301, 1989.
53. A. Czumaj, C. Riley, C. Scheideler, Perfectly balanced allocation. In: Proc. of the 7th Int. Workshop
on Randomized and Approximation Techniques in Computer Science (RAN-DOM’03), pp. 240–251,
2003.
54. J. Dai, S. Wang, Clustering-based interference management in densely deployment femtocell networks.
Digital Commun. and Netw., 2(4), 175–183, 2016.
55. A.P. Davies, E.E. Bischoff, Weight distribution considerations in container loading. EJOR 114(3),
509–527, 1999.
56. J.A. Davis, Clustering and structural balance in graphs. Human Relations, 20(2), 181–187, 1967.

18
57. P. Dell’Olmo, M.G. Speranza, Approximation algorithms for partitioning small items in unequal bins
to minimize the total size. Discr. Appl. Math., 94(1-3), 181–191, 1999.
58. P. Dell’Olmo, P. Hansen, S. Pallottino, G. Storchi, On uniform k-partition problem. Discr. Appl.
Math., 150(1–3), 121–139, 2005.
59. R. Diekmann, R. Preis, F. Schlimbach, C. Walshaw, Aspect ratio for mesh partitioning. In: Proc. of
Euro-Par’98, LNCS 1470, Springer, pp. 347–351, 1998.
60. R. Diekmann, R. Preis, F. Schlimbach, C. Walshaw, Shape-optimized mesh partitioning and load
balancing for parallel adaptive FEM. Paral. Comput., 26, 1555–1581, 2000.
61. A. Dolgui, Balancing assembly and transfer lines. EJOR, 168(3), 663–665, 2006.
62. A. Dolgui, N. Guschinsky, G. Levin, A special case of transfer lines balancing by graph approach.
EJOR, 168(3), 732–746, 2006.
63. P. Erdos, R. Faudree, E.T. Ordman, Clique partitions and clique coverings. Discr. Math., 72, 93–101,
1988.
64. E. Erel, S.C. Sarin, A survey of the assembly line balancing procedures. Production Planning and
Control, 9(5), 414–434, 1998.
65. S.K. Ethiraj, D. Levinthal, Modularity and innovation in complex systems. Manag. Sci. 50(2), 159–
173, 2004.
66. G. Even, J. Naor, S. Rao, B. Schieber, Fast approximate graph partitioning algorithms. SIAM J. on
Comput., 28(6), 2187–2214, 1999.
67. U. Faigle, W. Kern, On some approximately balanced combinatorial cooperative games. Zeitschrift
fur Operations Research, 38(2), 141–152, 1993.
68. A.E. Feldmann, Balanced partitioning of grids and related graphs: a theoretical study of data distribution in parallel finite element model simulation. Cuvilier ETH Zurich, 2012,
69. A.E. Feldmann, Fast balanced partitioning is hard even on grids and trees. Theor. Comp. Sci., 485,
61–68, 2013.
70. A.E. Feldmann, Fixed parameter approximations for k-center problems in low highway dimension
graphs. Electr. prepr., 15 p., May 9, 2016. http://arxiv.org/abs/1605.02530 []
71. A.E. Feldmann, L. Foschini, Balanced partitions of trees and applications. Algorithmica, 71(2), 354–
376, 2015.
72. T.A. Feo, M. Khellaf, A class of bonded approximation algorithms for graph partitioning. Networks,
20(2), 181–195, 1990.
73. T.A. Feo, O. Goldschmidt, M. Khellaf, One-half approximation algorithms for the k-partition problem. Oper. Res., 40, 170–173, 1992.
74. Y.-G. Fu, J. Zhou, L. Deng, Yi-Ge Fu, Jie Zhou, Lei Deng, Surveillance of a 2D plane area with 3D
deployment cameras. Sensors, 14(2), 1988–2011, 2014.
75. M.R. Garey, D.S. Johnson, Computers and Intractability. The Guide to the Theory of NPCompleteness. W.H. Freeman and Company, San Francisco, 1979.
76. B. Goldengorin, D. Ghosh, A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. of Glob. Optim., 32(1), 65–82, 2005.
77. G. Gupta, M. Younis, Load-balanced clustering of wireless sensor networks. In: IEEE Int. Conf. on
Communications ICC’03, vol. 3, pp. 1848–1852, 2003.
78. G.R. Gupta, N.B. Shroff, Practical scheduling schemes with throughput guaranties for multi-hop
wireless networks. Comp. Netw., 54(5), 766–780, 2010.
79. F. Harary, On the notion of balance in signed graph. Michigan math., 2, 143–146, 1953.
80. T.R. Hoffmann, Assembly line balancing: a set of challenging problems. Int. J. of Prod. Res., 28,
1807–1815, 1990.
81. G. Horn, B.J. Oommen, Towards a learning automata solution to the multi-constraint partitioning
problem. In: 2006 IEEE Conf. on Cybernetics and Intelligent Systems, pp. 1–8, 2006.
82. E. Horowitz, S. Sahni, Computing partitions with applications to the knapsack problem. J. of the
ACM, 21(2), 277–292, 1974.
83. J. Hromkovic, B. Monien, The bisection problem for graphs of degree 4 (configuring transputer
systems). In: 16th Symp. on Mathematical Foundations of Computer Science (MFCS), LNCS 520,
Springer, pp. 211–220, 1991.
84. N. Israr, A. Awan, Coverage based inter-cluster communication for load-balancing in heterogeneous

19
wireless sensor networks. Telecommun. Syst., 38, 121–132, 2008.
85. X. Ji, J.E. Mitchell, Branch-and-price-and-cut on the clique partitioning problem with minimum
clique size requirements. Discr. Optim., 4(1), 87–102, 2007.
86. A. Jose, M. Tollenaere, Modular and platform methods for product family design: literature analysis.
J. Intell. Manuf. 16, 371–390, 2005.
87. N. Jozefowiez, F. Semet, E.G. Talbi, An evolutionary algorithm for the vehicle routing problem with
route balancing. EJOR, 195(3), 761–769, 2009.
88. P.L. Karlton, S.H. Fuller, R.E. Scroggs, E.B. Kaehler, Performance of height-balanced trees. Commun.
of the ACM, 19(1), 23–28, 1976.
89. A.V. Kel’manov, S.A. Khamidullin, V. I. Khandeev, L. V. Mikhailova, An approximation algorithm
for one NP-hard problem of partitioning a sequence into clusters with restrictions on their cardinalities. In: Book of abstracts of the 11th Int. Conf. “Intelligent Data Processing” (IDP-2016), pp. 72–73,
2016.
90. K. Kenthapadi, R. Panigrahy, Balanced allocation on graphs. In: Proc. of the Seventeenth Annual
ACM-SIAM Symp. on Discrete Math., SIAM, pp. 434–443, 2006.
91. A.W. Khan, A.H. Abdullah, M.H. Anisi, J.I. Bangash, A comprehensive study of data collection
schemes using mobile sinks in wireless sensor networks. Sensors, 14(2), 2510–2548, 2014.
92. J.T. Kim, D.R. Shin, New efficient clique partitioning algorithms for register-transfer synthesis of
data paths. J. Korean Phys. Soc., 40, 754–758, 2002.
93. D. Knuth, The Art of computing Programming. Vol. 3: Sorting and Searching, 3rd ed., AddisonWesley, pp. 458—475, 1997.
94. R.E. Korf, A complete anytime algorithm for number partitioning. Artif. Intell., 106(2), 181–203,
1998.
95. R. Krauthgamer, J. Naor, R. Schwattz, Partitioning graphs into balanced components. In: Proc. of
the 20th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 942–949, 2009.
96. M.N. Kritikos, G. Ioannou, The balanced cargo vehicle routing problem with time windows. Int. J.
of Prod. Econ., 123(1), 42–51, 2010.
97. P. Kuila, S.K. Gupta, P.K. Jana, A novel evolutionary approach for load balanced clustering problem
for wireless sensor networks. Swarm and Evolution and Computation, 12, 48–56, 2013.
98. P. Kuila, P.K. Jana, Approximation schemes for load balanced clustering in wireless sensor networks.
The J. of Supercomput., 68(1), 87–105, 2014.
99. J. Leskovec, L. Backstrom, J. Kleinberg, Meme-tracking and the dynamics of the news cycle. In:
Proc. of the 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD’09),
pp. 497–506, 2009.
100.M.Sh. Levin, An extremal problem of organization of data. Eng. Cybern., 19(5), 87–95, 1981.
101.M.Sh. Levin, Multiset estimates and combinatorial synthesis. Electr. prepr., 30 p., May 9, 2012.
http://arxiv.org/abs/1205.2046 []
102.M.Sh. Levin, Towards design of system hierarchy (research survey). Electr. prepr., 36 p., Dec. 7, 2012.
http://arxiv.org/abs/1212.1735 [math.OC]
103.M.Sh. Levin, Modular System Design and Evaluation, Sprigner, 2015.
104.M.Sh. Levin, Towards combinatorial clustering: preliminary research survey. Electr. prepr., 102 p.,
May 28, 2015. http://arxiv.org/abs/1505.07872 []
105.M.Sh. Levin, On combinatorial clustering: literature review, methods, examples. J. of Commun.
Technol. and Electronics, 60(12), 1403–1428, 2015.
106.M.Sh. Levin, Data allocation on disks with solution reconfiguration (problems, heuristics). Elec.
prepr., 10 p., Dec. 18, 2016. http://arxiv.org/abs/1612.04519 [cs.DC]
107.Y. Liao, H. Qi, W. Li, Load-balanced clustering algorithm with distributed self-organization for
wireless sensor network. IEEE Sensors J., 13(5), 1498–1506, 2013.
108.A. Lim, B. Rodrigues, F. Wang, Zh. Xu, k-Center problem with minimum coverage. Theor. Comp.
Sci., 332(1–3), 1–17, 2005.
109.F.C.H. Lin, R.M. Keller, The gradient model load balancing method. IEEE Trans. on Software Engrg.,
13, 32–37, 1987.
110.X. Liu, A survey on clustering routing protocols in wireless sensor networks. Sensors, 12(8), 11113–
11153, 2012.

20
111.C.P. Low, C. Fang, J.M. Ng, Y.H. Ang, Efficient load-balanced clustering algorihtms for wireless
sensor networks. Comp. Commun., 31(4), 750–759, 2008.
112.J. Ma, G.E. Okudan Kremer, A systematic literature review of modular product design (MPD) from
the perspective of sustainability. Int. J. Adv. Manuf., 86(5), 1509–1539, 2016.
113.R.M. MacGegor, On Partitioning of Graphs: a Theoretical and Empirical Study. PhD thesis, Univ.
of California, Berkeley, 1978.
114.K. Mathur, An integer-programming-based heuristic for the balanced loading problem. Oper. Res.
Lett., 22(1), 19–25, 1998.
115.S. Mertens, A complete anytime algorithm for balanced number partitioning. Electr. prepr., 12 p.,
Mar. 9, 1999. http://arxiv.org/abs/9903011 []
116.H. Meyerhenke, P. Sanders, C. Schulz, Partitioning (hierarchically clustered) complex networks via
size-constrained graph clustering. J. of Heuristics, 22(5), 759–782, 2016.
117.A. Molnar, A General Partition Data Model and a Contribution to the Theory of Functional Dependencies. PhD thesis, Eotvos Lorand Univer., Faculty of Informatics, Hungary, 2007.
118.C.L. Monma, T. Carpenter, Variations on Matrix Balancing for Telecommunication Demand Forecasting. Technical Report, Telcordia, 1997.
119.S.B. Musunoori, G. Horn, Ant-based approach to the quality aware application service partitioning
in a grid environment. In: 2006 IEEE Int. Conf. on Evolutionary Computation, pp. 589–596, 2006.
120.S.B. Musunoori, G. Horn, Intelligent ant-based solution to the application service partitioning problem
in a grid environment. In: Sixth Int. Conf. on Intelligent Systems Design and Applications, vol. 1,
416–424, 2006.
121.L.M. Ni, K. Hwang, Optimal load balancing in a multiple processor system with many job classes.
IEEE Trans. on SE, 11(5), 491–496, 1985.
122.G. Nikolakopoulou, S. Kortesis, A. Synefaki, R. Kalfakakou, Solving a vehicle routing problem by
balancing the vehicles time utilization. EJOR, 152(2), 520–527, 2004.
123.C. Obreque, M. Donoso, G. Gutierrez, V. Marianov, A branch and cut algorithm for the hierarchical
network design problem. EJOR, 200(1), 28–35, 2010.
124.J. Oyola, A. Lokketangen, Grasp-asp: An algorithm for the cvrp with route balancing. J. of Heuristics,
20(4), 361–382, 2014.
125.V. Pandiri, A. Singh, Swarm intelligence approaches for multidepot salesmen problems with load
balancing. Applied Intelligence, 44(4), 849–861, 2016.
126.J. Pattillo, S. Butenko, Clique, independent set, and graph coloring. In: J. Cochran (ed), Encyclopedia
of Operations Research and Management Science, Wiley, pp. 3150–3163, 2011.
127.M. Pavan, M. Pelillo, Dominant sets and pairwise clustering. IEEE Trans. PAMI, 29(1), 167–172,
2007.
128.H. Pirkul, J. Current, V. Nagarajan, The hierarchical network design problem: A new formulation
and solution procedures. Transp. Sci., 25(3), 175–182, 1991.
129.S. Raisch, Balanced structures: Designing organizations for profitable growth. Long Range Planning,
41(5), 483–508, 2008.
130.A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, I. Stoica, Load balancing in structuring P2P
systems. In: Int. Workshop on Peer-to-Peer Systems, Springer, pp. 68–79, 2003.
131.D.M. Rayan, J.C. Falkner, On the integer properties of scheduling set partitioning models. EJOR,
35(3), 442–456, 1988.
132.R. Rees, Minimal clique partitions and pairwise balanced designs. Discr. Math., 61(2–3), 269–280,
1986.
133.F.R. Roberts, Discrete Mathematical Models with Applications Social, Biological and Environmental
Problems. Prentice Hall, Englewood Cliffs, NJ, 1976.
134.F.R. Roberts, Graph Theory and Its Applications to Problems of Society. SIAM, Philadelphia, 1976.
135.D. Saha, D. Menasce, S. Porto, Static and dynamic processor scheduling disciplines in heterogeneous
parallel architectures. J. of Parallel and Distributed Computing, 28(1), 1–18, 1995.
136.T. Sawik, Balancing and scheduling of surface mount technology lines. Int. J. of Prod. Res., 40(9),
1973–1991, 2002.
137.M.H. Schneider, S.A. Zenios, A comparative study of algorithms for matrix balancing. Oper. Res.,
38, 439–455, 1990.

21
138.R. Schoonderwoerd, O.E. Holland, J.L. Bruten, L.J. Rothkrantz, Ant-based load balancing in telecommunications networks. Adaptive Behavior, 5(2), 169–207, 1997.
139.W. Shang, J.A.B. Fortes, Independent partitioning of algorithms with uniform dependencies. IEEE
Trans. on Computers, 41(2), 190–206, 1992.
140.F. Shang, Y. Lei, An energy-balanced clustering routing algorithm for wireless sensor network. Wir.
Sens. Netw., 2(10), 777–783, 2010.
141.L.S. Shapley, On balanced sets and cores. Nav. Res. Log. Quart., 14, 453–460, 1967.
142.D. Simplot-Ryl, I. Stojmenovic, J. Wu, Energy efficient broadcasting, activity scheduling and area
coverage in sensor networks. In: I. Stojmenovic (ed), Handbook of Sensor networks: Algorithms and
Architectures, Wiley, pp. 343–379, 2005.
143.D.D. Sleater, R.E. Tarjan, Self-adjusting binary search trees. J. of the ACM, 32, 652–686, 1985.
144.M.M. Sorensen, Facet-defining inequalities for the simple graph partitioning polytope. Discr. Optim.,
4(2), 221–231, 2007.
145.L.-H. Tsai, Asymptotic analysis of an algorithm for balanced parallel processor scheduling. SIAM J.
Comput., 21(1), 59–64, 1992.
146.C. Walshaw. Variable partition inertia: Graph repartitioning and load balancing for adaptive meshes.
In: M. Parashar, X. Li (eds), Advanced Computational Infrastructures for Parallel and Distributed
Adaptive Applications, pp. 357-380. 2010.
147.C. Walshaw, M. Cross, Mesh partitioning: A multilevel balancing and refinement algorithm. SIAM
J. on Scient. Comput., 22(1), 63-80, 2000.
148.C. Walshaw, M. Cross. Multilevel mesh partitioning for heterogeneous communication networks. Fut.
Gen. Comp. Syst., 17(5), 601-623, 2001.
149.L. Wang, L. Da Xu, Z. Bi, Y. Xu, Data cleaning for RFID and WSN integration. IEEE Trans. on
Industrial Informatics, 10(1), 408–418, 2014.
150.E. Yildiz, K. Akkaya, E. Sisiloglu, M. Sir, Optimal camera placement for providing angular coverage
in wireless video sensor networks. IEEE Trans. on Computers, 63(7), 487–503, 2014.
151.O. Younis, S. Farmy, HEED: A hyubrid, energy-efficient, distributed clustering approach for Ad Hoc
sensor networks. IEEE Trans. on Mob. Comput., 3(4), 660–669, 2004.
152.O. Younis, M. Krinz, S. Ramasubramanian, Node clustering in wireless sensor networks: Recent
developments and deployment challenges. IEEE Networks, 20(3), 20–25, 2006.
153.S.A. Zenios, A. Drud, J.M. Mulvey, Balancing large social accounting matrices with nonlinear network
programming. Networks, 19, 569–585, 1989.
154.M. Zhao, Y. Yang, C. Wang, Mobile data gathering with load balanced clustering and dual data
uploading in wireless sensor networks. IEEE Trans. on Mob. Comput., 14(4), 770–785, 2015.

