NDLI: On Minimum Sum of Radii and Diameters Clustering

Content Provider	Springer Nature Link
Author	Behsaz, Babak Salavatipour, Mohammad R.
Copyright Year	2014
Abstract	Given a metric $$(V,d)$$ and an integer $$k$$ , we consider the problem of partitioning the points of $$V$$ into at most $$k$$ clusters so as to minimize the sum of radii or the sum of diameters of these clusters. The former problem is called the minimum sum of radii (MSR) problem and the latter is the minimum sum of diameters (MSD) problem. The current best polynomial time algorithms for these problems have approximation ratios 3.504 and 7.008, respectively. We call a cluster containing a single point, a singleton cluster. For the MSR problem when singleton clusters are not allowed, we give an exact algorithm for metrics induced by unweighted graphs. In addition, we show that in this case, a solution consisting of the best single cluster for each connected component of the graph is a $$\frac{3}{2}$$ -approximation algorithm. For the MSD problem on the plane with Euclidean distances, we present a polynomial time approximation scheme. In addition, we settle the open problem of complexity of the MSD problem with constant $$k$$ by giving a polynomial time exact algorithm in this case. The previously best known approximation algorithms for MSD on the plane or for MSD with constant $$k$$ have both ratio 2.
Starting Page	143
Ending Page	165
Page Count	23
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	73
Issue Number	1
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2014-07-04
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Clustering Minimum sum radii and diameters Euclidean metric Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On Metric Clustering to Minimize the Sum of Radii

Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions

Grade of Service Steiner Minimum Trees in the Euclidean Plane

Multicriteria Global Minimum Cuts

Exact and Approximation Algorithms for Clustering

Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals

Euclidean Prize-Collecting Steiner Forest

An Optimal Algorithm for the Minimum Disc Cover Problem

An Improved Algorithm for Online Unit Clustering

On Minimum Sum of Radii and Diameters Clustering

Similar Documents

On Metric Clustering to Minimize the Sum of Radii

Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions

Grade of Service Steiner Minimum Trees in the Euclidean Plane

Multicriteria Global Minimum Cuts

Exact and Approximation Algorithms for Clustering

Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals

Euclidean Prize-Collecting Steiner Forest

An Optimal Algorithm for the Minimum Disc Cover Problem

An Improved Algorithm for Online Unit Clustering

On Minimum Sum of Radii and Diameters Clustering