RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






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


Trudy Inst. Mat. i Mekh. UrO RAN, 2017, Volume 23, Number 3, Pages 159–170 (Mi timm1446)  

Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster

A. V. Kel'manovab, A. V. Motkovab, V. V. Shenmaiera

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University

Abstract: We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).

Keywords: Euclidean space, partitioning, NP-hardness, FPTAS, PTAS.

Funding Agency Grant Number
Russian Science Foundation 16-11-10041


DOI: https://doi.org/10.21538/0134-4889-2017-23-3-159-170

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

Bibliographic databases:

Document Type: Article
UDC: 519.16+519.85
MSC: 68W25, 68Q25
Received: 24.05.2017

Citation: A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Trudy Inst. Mat. i Mekh. UrO RAN, 23, no. 3, 2017, 159–170

Citation in format AMSBIB
\Bibitem{KelMotShe17}
\by A.~V.~Kel'manov, A.~V.~Motkova, V.~V.~Shenmaier
\paper Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2017
\vol 23
\issue 3
\pages 159--170
\mathnet{http://mi.mathnet.ru/timm1446}
\crossref{https://doi.org/10.21538/0134-4889-2017-23-3-159-170}
\elib{http://elibrary.ru/item.asp?id=29938008}


Linking options:
  • http://mi.mathnet.ru/eng/timm1446
  • http://mi.mathnet.ru/eng/timm/v23/i3/p159

    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
  • Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Number of views:
    This page:86
    Full text:8
    References:13
    First page:9

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