The inverse p-maxian problem on trees with variable edge lengths

الأصل · EN

We concern the problem of modifying the edge lengths of a tree in minimum total cost so that the prespecified p vertices become the p-maxian with respect to the new edge lengths. This problem is called the inverse p-maxian problem on trees. Gassner proposed efficient combinatorial alogrithm to solve the the inverse 1-maxian problem on trees in 2008. For the problem with p ≥ 2, we claim that the problem can be reduced to finitely many inverse 2-maxian problem. We then develop algorithms to solve the inverse 2-maxian problem for various objective functions. The problem under l₁-norm can be formulated as a linear program and thus can be solved in polynomial time. Particularly, if the underlying tree is a star, then the problem can be solved in linear time. We also devised O(n n) algorithms to solve the problems under Chebyshev norm and bottleneck Hamming distance, where n is the number of vertices of the tree. Finally, the problem under weighted sum Hamming distance is NP-hard.