RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

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


Diskretn. Anal. Issled. Oper., 2010, Volume 17, Number 3, Pages 19–31 (Mi da609)  

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

On probabilistic analysis of one approximation algorithm for the $p$-median problem

E. Kh. Gimadiab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

Abstract: An approximation algorithm for solving the $p$-median problem with time complexity $O(n^2)$ and results of its probabilistic analysis are presented. Given an undirected complete graph with distances that are independent random uniformly distributed variables. The objective equals the sum of the random variables. Analysis is based on estimations of the probability of great deviations of those sums. In the paper one of limit theorems for this analysis in the form of Petrov's inequality is used. Moreover, the dependence factor is taken into account. As the results of the probabilistic analysis, the bounds of the relative error, the fault probability and conditions of asymptotic optimality of the algorithm are presented. Ill. 1, bibl. 11.

Keywords: $p$-median problem, approximation algorithm, asymptotic optimality, relative error, fault probability, Petrov's theorem, uniform distribution.

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

Bibliographic databases:
UDC: 519.8
Received: 26.10.2009
Revised: 27.12.2009

Citation: E. Kh. Gimadi, “On probabilistic analysis of one approximation algorithm for the $p$-median problem”, Diskretn. Anal. Issled. Oper., 17:3 (2010), 19–31

Citation in format AMSBIB
\Bibitem{Gim10}
\by E.~Kh.~Gimadi
\paper On probabilistic analysis of one approximation algorithm for the $p$-median problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2010
\vol 17
\issue 3
\pages 19--31
\mathnet{http://mi.mathnet.ru/da609}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2732271}
\zmath{https://zbmath.org/?q=an:1249.90140}


Linking options:
  • http://mi.mathnet.ru/eng/da609
  • http://mi.mathnet.ru/eng/da/v17/i3/p19

    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

    This publication is cited in the following articles:
    1. E. Kh. Gimadi, V. T. Dementev, “Veroyatnostnyi analiz detsentralizovannoi versii odnogo obobscheniya zadachi o naznacheniyakh”, Diskretn. analiz i issled. oper., 18:3 (2011), 11–20  mathnet  mathscinet  zmath
    2. E. Kh. Gimadi, A. V. Shakhshneyder, “Approximate algorithms with estimates for routing problems on random inputs with a bounded number of customers per route”, Autom. Remote Control, 73:2 (2012), 323–335  mathnet  crossref  isi
  • Дискретный анализ и исследование операций
    Number of views:
    This page:389
    Full text:95
    References:35
    First page:8

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