Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretnyi Analiz i Issledovanie Operatsii, 2010, Volume 17, Issue 6, Pages 3–19 (Mi da627)  

This article is cited in 14 scientific papers (total in 14 papers)

Approximation algorithms for the competitive facility location problem

V. L. Beresnevab, A. A. Melnikovb

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
References:
Abstract: The paper deals with the competitive facility location problem, where two players, the leader and the follower, sequentially establish their facilities and every consumer chooses one of the established facilities in accordance with his own preference. The problem consists in placing the leader's facilities so as to acquire the maximal profit, taking the follower's facilities placing into account, who seeks to maximize his profit as well. The problem is formulated in terms of bi-level integer programming. The paper offers a method for calculating the upper bound for the leader's maximum profit value. The corresponding algorithm consists in designing the classical maximization facility location problem and finding its optimal solution. Along with the calculation of the upper bound, an initial approximate solution for the problem of competitive facility location is generated. The paper offers local search algorithms for improving the initial approximate solution and gives the results of a computational experiment employing the proposed algorithms. The experiment makes it possible to estimate the precision of the obtained approximate solutions and a comparative evaluation of the quality of the algorithms under examination for designing approximate solutions of the examined problem. Tab. 1, bibliogr. 13.
Keywords: bi-level programming problem, optimal uncooperative solution, upper bound, approximate solution, local search.
Received: 10.05.2010
Bibliographic databases:
Document Type: Article
UDC: 519.725
Language: Russian
Citation: V. L. Beresnev, A. A. Melnikov, “Approximation algorithms for the competitive facility location problem”, Diskretn. Anal. Issled. Oper., 17:6 (2010), 3–19
Citation in format AMSBIB
\Bibitem{BerMel10}
\by V.~L.~Beresnev, A.~A.~Melnikov
\paper Approximation algorithms for the competitive facility location problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2010
\vol 17
\issue 6
\pages 3--19
\mathnet{http://mi.mathnet.ru/da627}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2797613}
\zmath{https://zbmath.org/?q=an:1249.90138}
Linking options:
  • https://www.mathnet.ru/eng/da627
  • https://www.mathnet.ru/eng/da/v17/i6/p3
  • This publication is cited in the following 14 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Statistics & downloads:
    Abstract page:792
    Full-text PDF :176
    References:62
    First page:6
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024