The Planar k-Means Problem is NP-Hard View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Meena Mahajan , Prajakta Nimbhorkar , Kasturi Varadarajan

ABSTRACT

In the k-means problem, we are given a finite set S of points in , and integer k ≥ 1, and we want to find k points (centers) so as to minimize the sum of the square of the Euclidean distance of each point in S to its nearest center. We show that this well-known problem is NP-hard even for instances in the plane, answering an open question posed by Dasgupta [6]. More... »

PAGES

274-285

References to SciGraph publications

Book

TITLE

WALCOM: Algorithms and Computation

ISBN

978-3-642-00201-4
978-3-642-00202-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_24

DOI

http://dx.doi.org/10.1007/978-3-642-00202-1_24

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1048907538


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0601", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biochemistry and Cell Biology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.462414.1", 
          "name": [
            "The Institute of Mathematical Sciences, 600 113, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mahajan", 
        "givenName": "Meena", 
        "id": "sg:person.015704527337.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015704527337.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.462414.1", 
          "name": [
            "The Institute of Mathematical Sciences, 600 113, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nimbhorkar", 
        "givenName": "Prajakta", 
        "id": "sg:person.015537550337.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015537550337.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Iowa", 
          "id": "https://www.grid.ac/institutes/grid.214572.7", 
          "name": [
            "The University of Iowa, IA 52242-1419, Iowa City, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Varadarajan", 
        "givenName": "Kasturi", 
        "id": "sg:person.012631122265.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012631122265.92"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00453-004-1127-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012019308", 
          "https://doi.org/10.1007/s00453-004-1127-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10994-009-5103-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013120388", 
          "https://doi.org/10.1007/s10994-009-5103-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/177424.178042", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017563529"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/b:mach.0000033113.59016.96", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022292789", 
          "https://doi.org/10.1023/b:mach.0000033113.59016.96"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11590156_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030013760", 
          "https://doi.org/10.1007/11590156_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11590156_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030013760", 
          "https://doi.org/10.1007/11590156_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1137856.1137880", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039920405"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/780542.780550", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048702328"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.comgeo.2004.03.003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048832528"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1981.6312176", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061532644"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1982.1056489", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061648677"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0211025", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841641"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0213014", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841748"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2004.7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093944225"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2006.75", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095405530"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2006.79", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095694740"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "In the k-means problem, we are given a finite set S of points in , and integer k \u2265 1, and we want to find k points (centers) so as to minimize the sum of the square of the Euclidean distance of each point in S to its nearest center. We show that this well-known problem is NP-hard even for instances in the plane, answering an open question posed by Dasgupta [6].", 
    "editor": [
      {
        "familyName": "Das", 
        "givenName": "Sandip", 
        "type": "Person"
      }, 
      {
        "familyName": "Uehara", 
        "givenName": "Ryuhei", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-00202-1_24", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-00201-4", 
        "978-3-642-00202-1"
      ], 
      "name": "WALCOM: Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "The Planar k-Means Problem is NP-Hard", 
    "pagination": "274-285", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-00202-1_24"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e8fc5fc3d57c603ddf448609283e442c100853dc27ea90a4040011a6ed270eaf"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048907538"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-00202-1_24", 
      "https://app.dimensions.ai/details/publication/pub.1048907538"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T06:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000351_0000000351/records_43266_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-00202-1_24"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_24'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_24'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00202-1_24'


 

This table displays all metadata directly associated to this object as RDF triples.

136 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-00202-1_24 schema:about anzsrc-for:06
2 anzsrc-for:0601
3 schema:author N72f9bcd1f081476ca9f075dda137f1e9
4 schema:citation sg:pub.10.1007/11590156_19
5 sg:pub.10.1007/s00453-004-1127-9
6 sg:pub.10.1007/s10994-009-5103-0
7 sg:pub.10.1023/b:mach.0000033113.59016.96
8 https://doi.org/10.1016/j.comgeo.2004.03.003
9 https://doi.org/10.1109/focs.2004.7
10 https://doi.org/10.1109/focs.2006.75
11 https://doi.org/10.1109/focs.2006.79
12 https://doi.org/10.1109/tc.1981.6312176
13 https://doi.org/10.1109/tit.1982.1056489
14 https://doi.org/10.1137/0211025
15 https://doi.org/10.1137/0213014
16 https://doi.org/10.1145/1137856.1137880
17 https://doi.org/10.1145/177424.178042
18 https://doi.org/10.1145/780542.780550
19 schema:datePublished 2009
20 schema:datePublishedReg 2009-01-01
21 schema:description In the k-means problem, we are given a finite set S of points in , and integer k ≥ 1, and we want to find k points (centers) so as to minimize the sum of the square of the Euclidean distance of each point in S to its nearest center. We show that this well-known problem is NP-hard even for instances in the plane, answering an open question posed by Dasgupta [6].
22 schema:editor N0a328d2e0af3458e8fbc3a05d47e5968
23 schema:genre chapter
24 schema:inLanguage en
25 schema:isAccessibleForFree true
26 schema:isPartOf Nfe2322b15a3441ecbd231c7c1c286aaa
27 schema:name The Planar k-Means Problem is NP-Hard
28 schema:pagination 274-285
29 schema:productId N080c6de54fa74d65a07957f788ff0b38
30 N1a6daf834cc64e9da421a4e8273028bc
31 N41871b86c2d64969bcb86489ec90b395
32 schema:publisher N828ae6105412425ca767a66618119bab
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048907538
34 https://doi.org/10.1007/978-3-642-00202-1_24
35 schema:sdDatePublished 2019-04-16T06:16
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher Nc415502fb0354837a881e599051ae81b
38 schema:url https://link.springer.com/10.1007%2F978-3-642-00202-1_24
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N080c6de54fa74d65a07957f788ff0b38 schema:name dimensions_id
43 schema:value pub.1048907538
44 rdf:type schema:PropertyValue
45 N0a328d2e0af3458e8fbc3a05d47e5968 rdf:first Nd50520bed8184654bc622387233695f0
46 rdf:rest N4c2610a80eed43bfae8a7628de0a0c76
47 N1a6daf834cc64e9da421a4e8273028bc schema:name readcube_id
48 schema:value e8fc5fc3d57c603ddf448609283e442c100853dc27ea90a4040011a6ed270eaf
49 rdf:type schema:PropertyValue
50 N1a782c3ab9234a40ae2e7f2b4f4bc141 schema:familyName Uehara
51 schema:givenName Ryuhei
52 rdf:type schema:Person
53 N41871b86c2d64969bcb86489ec90b395 schema:name doi
54 schema:value 10.1007/978-3-642-00202-1_24
55 rdf:type schema:PropertyValue
56 N4c2610a80eed43bfae8a7628de0a0c76 rdf:first N1a782c3ab9234a40ae2e7f2b4f4bc141
57 rdf:rest rdf:nil
58 N72f9bcd1f081476ca9f075dda137f1e9 rdf:first sg:person.015704527337.23
59 rdf:rest N8e4366626bbd4be0a197d30dd04b5ca2
60 N828ae6105412425ca767a66618119bab schema:location Berlin, Heidelberg
61 schema:name Springer Berlin Heidelberg
62 rdf:type schema:Organisation
63 N8e4366626bbd4be0a197d30dd04b5ca2 rdf:first sg:person.015537550337.02
64 rdf:rest Ncfbfe3b3228544478f45dbdbb570e637
65 Nc415502fb0354837a881e599051ae81b schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Ncfbfe3b3228544478f45dbdbb570e637 rdf:first sg:person.012631122265.92
68 rdf:rest rdf:nil
69 Nd50520bed8184654bc622387233695f0 schema:familyName Das
70 schema:givenName Sandip
71 rdf:type schema:Person
72 Nfe2322b15a3441ecbd231c7c1c286aaa schema:isbn 978-3-642-00201-4
73 978-3-642-00202-1
74 schema:name WALCOM: Algorithms and Computation
75 rdf:type schema:Book
76 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
77 schema:name Biological Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0601 schema:inDefinedTermSet anzsrc-for:
80 schema:name Biochemistry and Cell Biology
81 rdf:type schema:DefinedTerm
82 sg:person.012631122265.92 schema:affiliation https://www.grid.ac/institutes/grid.214572.7
83 schema:familyName Varadarajan
84 schema:givenName Kasturi
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012631122265.92
86 rdf:type schema:Person
87 sg:person.015537550337.02 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
88 schema:familyName Nimbhorkar
89 schema:givenName Prajakta
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015537550337.02
91 rdf:type schema:Person
92 sg:person.015704527337.23 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
93 schema:familyName Mahajan
94 schema:givenName Meena
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015704527337.23
96 rdf:type schema:Person
97 sg:pub.10.1007/11590156_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030013760
98 https://doi.org/10.1007/11590156_19
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/s00453-004-1127-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012019308
101 https://doi.org/10.1007/s00453-004-1127-9
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/s10994-009-5103-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013120388
104 https://doi.org/10.1007/s10994-009-5103-0
105 rdf:type schema:CreativeWork
106 sg:pub.10.1023/b:mach.0000033113.59016.96 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022292789
107 https://doi.org/10.1023/b:mach.0000033113.59016.96
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/j.comgeo.2004.03.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048832528
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1109/focs.2004.7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093944225
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1109/focs.2006.75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095405530
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/focs.2006.79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095694740
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1109/tc.1981.6312176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532644
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1109/tit.1982.1056489 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061648677
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1137/0211025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841641
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1137/0213014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841748
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1145/1137856.1137880 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039920405
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1145/177424.178042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017563529
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1145/780542.780550 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048702328
130 rdf:type schema:CreativeWork
131 https://www.grid.ac/institutes/grid.214572.7 schema:alternateName University of Iowa
132 schema:name The University of Iowa, IA 52242-1419, Iowa City, USA
133 rdf:type schema:Organization
134 https://www.grid.ac/institutes/grid.462414.1 schema:alternateName Institute of Mathematical Sciences
135 schema:name The Institute of Mathematical Sciences, 600 113, Chennai, India
136 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...