• PDF
• Cite
• Share
Article Contents  Article Contents

# Inverse group 1-median problem on trees

• * Corresponding author: Van Huy Pham
• In location theory, group median generalizes the concepts of both median and center. We address in this paper the problem of modifying vertex weights of a tree at minimum total cost so that a prespecified vertex becomes a group 1-median with respect to the new weights. We call this problem the inverse group 1-median on trees. To solve the problem, we first reformulate the optimality criterion for a vertex being a group 1-median of the tree. Based on this result, we prove that the problem is $NP$-hard. Particularly, the corresponding problem with exactly two groups is however solvable in $O(n^2\log n)$ time, where $n$ is the number of vertices in the tree.

Mathematics Subject Classification: 90B10, 90B80, 90C27.

 Citation: • • Figure 1.  An instance of the inverse 2-group 1-median problem on trees

Table 1.  An instance of the inverse 2-group 1-median problem

 $j$ 1 2 3 5 $\bar{q}^1_j$ 0 0 0 0 $\bar{q}^2_j$ 0 0 0 - $\bar{p}^1_j$ 0 0 0 3 $\bar{p}^2_j$ 0 0 16 -

Table 2.  An instance of the subproblem $(P^1_{v^1_4})$ Table 3.  Cost values at breakpoints

 $t$ 8 10 18 20 $C(t)$ 46 44 49 56
• Figures(1)

Tables(3)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint