Branding/Logomark minus Citation Combined Shape Icon/Bookmark-empty Icon/Copy Icon/Collection Icon/Close Copy 7 no author result Created with Sketch. Icon/Back Created with Sketch. Match!

On the Existence of an Integer Solution to the Relaxed Weber Problem for a Tree Network

Published on Jul 1, 2019in Automation and Remote Control 0.59
· DOI :10.1134/S0005117919070063
Anatoly V. Panyukov4
Estimated H-index: 4
(SUSU: South Ural State University)
Cite
Abstract
The problem of finding an optimal location of the vertices of a tree network in an assembly space representing a finite set is considered. The optimality criterion is the minimum total cost of location and communications in all points of this space. Different vertices of the tree can be located in a single point of the assembly space. This problem is well-known as the Weber problem. The representation of the Weber problem as a linear programming problem is given. It is proved that the set of all optimal solutions to the corresponding relaxed Weber problem for the tree network contains an integer solution. This fact can be used to improve the efficiency of algorithms for the problems differing from the Weber problem by the presence of additional constraints: it allows us to find the optimal value of the objective function, which in turn significantly reduces the complexity of calculating the optimal solution itself, e.g., by the branch-and-bound method.
  • References (1)
  • Citations (0)
Cite
References1
Newest
Published on Jun 26, 1991in Journal of Computational and Applied Mathematics 1.88
Anatoly V. Panyukov4
Estimated H-index: 4
,
Boris V. Pelzwerger1
Estimated H-index: 1
Abstract A polynomial algorithm to a finite Veber problem for a tree network is presented. Space- and time-complexity estimations of this algorithm are given. The space complexity of this algorithm may be decreased for problems with an algorithmic representation of some input data. Examples of such problems and algorithms to them are
Published on Jan 1, 1975in Mathematics of Computation 2.09
Donald E. Knuth78
Estimated H-index: 78
Cited By0
Newest