Instance Results

These are the results of problem instances given here in this benchmark. Each instance is described using a table specifying the power required to by each agent to communicate with each other agent. Agents that cannot communicate are indicated with a dash (-). The source agent (i.e. the source device in the broadcast tree) is highlighted in red. The optimal result is highlighted in the table as follows: each row of the table represents an agent a_i; the table cells marked in yellow indicates that a_i is broadcasting to the corresponding other agent in the optimal broadcast tree. The optimal solution cost is the sum of the maximum highlighted value in each row.

Instances

Instance 1. Optimal cost = 19

Agent	a1	a2	a3	a4
a1	-	5	48	1
a2	5	-	13	33
a3	48	13	-	79
a4	1	33	79	-

Instance 2. Optimal cost = 183

Agent	a1	a2	a3	a4
a1	-	93	3	-
a2	93	-	142	183
a3	3	142	-	-
a4	-	183	-	-

Instance 3. Optimal cost = 124

Agent	a1	a2	a3	a4	a5	a6
a1	-	-	48	107	-	-
a2	-	-	-	1	26	48
a3	48	-	-	124	-	-
a4	107	1	124	-	21	68
a5	-	26	-	21	-	3
a6	-	48	-	68	3	-

Instance 4. Optimal cost = 232

Agent	a1	a2	a3	a4	a5	a6
a1	-	-	-	13	21	3
a2	-	-	68	-	-	-
a3	-	68	-	-	162	183
a4	13	-	-	-	68	68
a5	21	-	162	68	-	2
a6	3	-	183	68	2	-

Instance 5. Optimal cost = 340

Agent	a1	a2	a3	a4	a5	a6	a7	a8
a1	-	183	-	-	183	107	-	124
a2	183	-	17	33	183	162	-	-
a3	-	17	-	68	-	-	21	-
a4	-	33	68	-	124	-	-	-
a5	183	183	-	124	-	-	-	-
a6	107	162	-	-	-	-	-	68
a7	-	-	21	-	-	-	-	-
a8	124	-	-	-	-	68	-	-

Instance 6. Optimal cost = 293

Agent	a1	a2	a3	a4	a5	a6	a7	a8
a1	-	-	68	-	40	40	-	57
a2	-	-	-	-	-	-	-	21
a3	68	-	-	-	-	-	-	-
a4	-	-	-	-	79	21	183	-
a5	40	-	-	79	-	1	-	57
a6	40	-	-	21	1	-	-	142
a7	-	-	-	183	-	-	-	-
a8	57	21	-	-	57	142	-	-

Instance 7. Optimal cost = 417

Agent	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10
a1	-	-	-	-	162	-	-	-	17	5
a2	-	-	5	21	-	-	-	-	-	-
a3	-	5	-	48	68	-	-	-	-	-
a4	-	21	48	-	93	93	-	-	-	-
a5	162	-	68	93	-	-	-	-	-	124
a6	-	-	-	93	-	-	-	-	-	-
a7	-	-	-	-	-	-	-	33	-	57
a8	-	-	-	-	-	-	33	-	-	-
a9	17	-	-	-	-	-	-	-	-	107
a10	5	-	-	-	124	-	57	-	107	-

Instance 8. Optimal cost = 467

Agent	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10
a1	-	-	-	-	142	-	-	-	-	93
a2	-	-	13	-	-	-	-	-	79	-
a3	-	13	-	-	-	-	-	-	7	107
a4	-	-	-	-	124	-	162	-	-	-
a5	142	-	-	124	-	-	107	-	-	-
a6	-	-	-	-	-	-	57	7	-	-
a7	-	-	-	162	107	57	-	48	-	-
a8	-	-	-	-	-	7	48	-	-	-
a9	-	79	7	-	-	-	-	-	-	33
a10	93	-	107	-	-	-	-	-	33	-

Instance 9. Optimal cost = 748

Agent	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
a1	-	-	-	142	-	-	68	-	-	-	-	-
a2	-	-	93	142	-	-	-	-	79	68	-	-
a3	-	93	-	-	13	-	-	183	-	-	-	57
a4	142	142	-	-	-	-	-	-	2	57	-	-
a5	-	-	13	-	-	-	-	-	-	-	-	3
a6	-	-	-	-	-	-	-	57	-	-	124	-
a7	68	-	-	-	-	-	-	-	-	-	-	-
a8	-	-	183	-	-	57	-	-	-	-	-	183
a9	-	79	-	2	-	-	-	-	-	26	-	-
a10	-	68	-	57	-	-	-	-	26	-	-	-
a11	-	-	-	-	-	124	-	-	-	-	-	-
a12	-	-	57	-	3	-	-	183	-	-	-	-

Instance 10. Optimal cost = 600

Agent	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
a1	-	-	-	-	-	-	-	-	93	-	-	-
a2	-	-	-	-	-	-	10	-	-	-	-	107
a3	-	-	-	107	107	-	-	162	-	-	-	-
a4	-	-	107	-	-	93	-	183	-	-	-	-
a5	-	-	107	-	-	-	-	107	-	-	-	-
a6	-	-	-	93	-	-	-	-	7	-	68	-
a7	-	10	-	-	-	-	-	-	-	-	-	124
a8	-	-	162	183	107	-	-	-	-	48	-	21
a9	93	-	-	-	-	7	-	-	-	-	-	-
a10	-	-	-	-	-	-	-	48	-	-	-	21
a11	-	-	-	-	-	68	-	-	-	-	-	-
a12	-	107	-	-	-	-	124	21	-	21	-	-