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

  • 2005. The Directed Planar Reachability Problem in FSTTCS 2005: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 2004-07. Clustering Large Graphs via the Singular Value Decomposition in MACHINE LEARNING
  • 2009-05. NP-hardness of Euclidean sum-of-squares clustering in MACHINE LEARNING
  • 2005-03. How Fast Is the k-Means Method? in ALGORITHMICA
  • 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 Nff48f1e78d9d418da286c10f7cd38b4b
    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 Nd14bc8dcd333441da19963303c1b7b7c
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree true
    26 schema:isPartOf N51a6441f0573491fba41db2cfc8a4771
    27 schema:name The Planar k-Means Problem is NP-Hard
    28 schema:pagination 274-285
    29 schema:productId N127c32b4ed4e471e8c7997293b53ca53
    30 N25c2102ed6e3466c82191dadee85e3af
    31 Nb6ebbe8976b54e1a9ae042e2a839f273
    32 schema:publisher N715d89595f04492e928e523702769a63
    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 N039eac5ca68849978e500124591ed3cf
    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 N039eac5ca68849978e500124591ed3cf schema:name Springer Nature - SN SciGraph project
    43 rdf:type schema:Organization
    44 N09bde3e025574258bededb6c686d6050 rdf:first N6a6fe10cdd974a61a49df89b8bf88d59
    45 rdf:rest rdf:nil
    46 N127c32b4ed4e471e8c7997293b53ca53 schema:name doi
    47 schema:value 10.1007/978-3-642-00202-1_24
    48 rdf:type schema:PropertyValue
    49 N25c2102ed6e3466c82191dadee85e3af schema:name readcube_id
    50 schema:value e8fc5fc3d57c603ddf448609283e442c100853dc27ea90a4040011a6ed270eaf
    51 rdf:type schema:PropertyValue
    52 N51a6441f0573491fba41db2cfc8a4771 schema:isbn 978-3-642-00201-4
    53 978-3-642-00202-1
    54 schema:name WALCOM: Algorithms and Computation
    55 rdf:type schema:Book
    56 N6a6fe10cdd974a61a49df89b8bf88d59 schema:familyName Uehara
    57 schema:givenName Ryuhei
    58 rdf:type schema:Person
    59 N715d89595f04492e928e523702769a63 schema:location Berlin, Heidelberg
    60 schema:name Springer Berlin Heidelberg
    61 rdf:type schema:Organisation
    62 Nb6ebbe8976b54e1a9ae042e2a839f273 schema:name dimensions_id
    63 schema:value pub.1048907538
    64 rdf:type schema:PropertyValue
    65 Nb9ac1c63775a47479b517bfe910b7033 schema:familyName Das
    66 schema:givenName Sandip
    67 rdf:type schema:Person
    68 Nc1b0d05ecf1243809fb32b1c9a19439e rdf:first sg:person.012631122265.92
    69 rdf:rest rdf:nil
    70 Nd14bc8dcd333441da19963303c1b7b7c rdf:first Nb9ac1c63775a47479b517bfe910b7033
    71 rdf:rest N09bde3e025574258bededb6c686d6050
    72 Ne02e97d5977f41ed8d327f68fba27423 rdf:first sg:person.015537550337.02
    73 rdf:rest Nc1b0d05ecf1243809fb32b1c9a19439e
    74 Nff48f1e78d9d418da286c10f7cd38b4b rdf:first sg:person.015704527337.23
    75 rdf:rest Ne02e97d5977f41ed8d327f68fba27423
    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)


    ...