RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik YuUrGU. Ser. Mat. Model. Progr.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik YuUrGU. Ser. Mat. Model. Progr., 2019, Volume 12, Issue 1, Pages 150–155 (Mi vyuru480)  

Short Notes

On the existence of an integer solution of the relaxed Weber problem for a tree network

A. V. Panyukov

South Ural State University, Chelyabinsk, Russian Federation

Abstract: The problem of finding the optimal arrangement of vertices of a tree network in the installation space representing a finite set is considered. The criterion of optimality is the minimization of the total cost of deployment and the cost of communications. Placement of different tree vertices in one point of the installation space is allowed. This problem is known as Weber problem for a tree network. The statement of Weber problem as an integer linear programming problem is given in this research. It's proved that a set of optimal solutions of corresponding relaxed Weber problem for a tree-network contains the integer solution. This fact allows to prove the existence a saddle point while proving the performance of decomposition algorithms for problems different from problems because of additional restrictions.

Keywords: itshape allocation problem, linear programming, duality, relaxation, integer solution, polynomial algorithm, Weber problem.

DOI: https://doi.org/10.14529/mmp190114

Full text: PDF file (154 kB)
References: PDF file   HTML file

UDC: 519.688
MSC: 68Q25, 90C27, 49M20
Received: 03.08.2018
Language:

Citation: A. V. Panyukov, “On the existence of an integer solution of the relaxed Weber problem for a tree network”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 12:1 (2019), 150–155

Citation in format AMSBIB
\Bibitem{Pan19}
\by A.~V.~Panyukov
\paper On the existence of an integer solution of the relaxed Weber problem for a tree network
\jour Vestnik YuUrGU. Ser. Mat. Model. Progr.
\yr 2019
\vol 12
\issue 1
\pages 150--155
\mathnet{http://mi.mathnet.ru/vyuru480}
\crossref{https://doi.org/10.14529/mmp190114}
\elib{http://elibrary.ru/item.asp?id=37092215}


Linking options:
  • http://mi.mathnet.ru/eng/vyuru480
  • http://mi.mathnet.ru/eng/vyuru/v12/i1/p150

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:30
    Full text:9
    References:8

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019