Selecting a subset of diverse points based on the squared euclidean distance View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2021-09-22

AUTHORS

Anton V. Eremeev, Alexander V. Kel’manov, Mikhail Y. Kovalyov, Artem V. Pyatkin

ABSTRACT

In this paper we consider two closely related problems of selecting a diverse subset of points with respect to squared Euclidean distance. Given a set of points in Euclidean space, the first problem is to find a subset of a specified size M maximizing the sum of squared Euclidean distances between the chosen points. The second problem asks for a minimum cardinality subset of points, given a constraint on the sum of squared Euclidean distances between them. We consider the computational complexity of both problems and propose exact dynamic programming algorithms in the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, these algorithms have a pseudo-polynomial time complexity. We also develop an FPTAS for the special case of the first problem, where the dimension of the Euclidean space is bounded by a constant. More... »

PAGES

1-13

References to SciGraph publications

  • 2012-07. An approximation scheme for a problem of search for a vector subset in JOURNAL OF APPLIED AND INDUSTRIAL MATHEMATICS
  • 2009-06-30. Composing medical crews with equity and efficiency in CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH
  • 2014-07. An FPTAS for a vector subset search problem in JOURNAL OF APPLIED AND INDUSTRIAL MATHEMATICS
  • 2016-10. Solving some vector subset problems by Voronoi diagrams in JOURNAL OF APPLIED AND INDUSTRIAL MATHEMATICS
  • 2012-02-15. Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems in AUTOMATION AND REMOTE CONTROL
  • 2011-07. NP-completeness of some problems of choosing a vector subset in JOURNAL OF APPLIED AND INDUSTRIAL MATHEMATICS
  • 2019-06-12. Maximum Diversity Problem with Squared Euclidean Distance in MATHEMATICAL OPTIMIZATION THEORY AND OPERATIONS RESEARCH
  • 2020-07-18. On Finding Minimum Cardinality Subset of Vectors with a Constraint on the Sum of Squared Euclidean Pairwise Distances in LEARNING AND INTELLIGENT OPTIMIZATION
  • 2018-11-29. Some Easy and Some Not so Easy Geometric Optimization Problems in APPROXIMATION AND ONLINE ALGORITHMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10472-021-09773-z

    DOI

    http://dx.doi.org/10.1007/s10472-021-09773-z

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia", 
              "id": "http://www.grid.ac/institutes/grid.426295.e", 
              "name": [
                "Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Eremeev", 
            "givenName": "Anton V.", 
            "id": "sg:person.015645525051.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015645525051.36"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia", 
              "id": "http://www.grid.ac/institutes/grid.426295.e", 
              "name": [
                "Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kel\u2019manov", 
            "givenName": "Alexander V.", 
            "id": "sg:person.012666512667.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012666512667.93"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "United Institute of Informatics Problems, Minsk, Belarus", 
              "id": "http://www.grid.ac/institutes/grid.426549.8", 
              "name": [
                "United Institute of Informatics Problems, Minsk, Belarus"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kovalyov", 
            "givenName": "Mikhail Y.", 
            "id": "sg:person.015744710763.41", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015744710763.41"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia", 
              "id": "http://www.grid.ac/institutes/grid.426295.e", 
              "name": [
                "Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pyatkin", 
            "givenName": "Artem V.", 
            "id": "sg:person.016544210352.26", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016544210352.26"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1134/s0005117912020129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048959771", 
              "https://doi.org/10.1134/s0005117912020129"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1134/s1990478911030069", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008382823", 
              "https://doi.org/10.1134/s1990478911030069"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1134/s1990478914030041", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045548031", 
              "https://doi.org/10.1134/s1990478914030041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10100-009-0093-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011157397", 
              "https://doi.org/10.1007/s10100-009-0093-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-22629-9_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1117044082", 
              "https://doi.org/10.1007/978-3-030-22629-9_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1134/s1990478912030131", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036516748", 
              "https://doi.org/10.1134/s1990478912030131"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1134/s199047891604013x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042531934", 
              "https://doi.org/10.1134/s199047891604013x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-53552-0_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1129443842", 
              "https://doi.org/10.1007/978-3-030-53552-0_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-04693-4_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1110287584", 
              "https://doi.org/10.1007/978-3-030-04693-4_1"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-09-22", 
        "datePublishedReg": "2021-09-22", 
        "description": "In this paper we consider two closely related problems of selecting a diverse subset of points with respect to squared Euclidean distance. Given a set of points in Euclidean space, the first problem is to find a subset of a specified size M maximizing the sum of squared Euclidean distances between the chosen points. The second problem asks for a minimum cardinality subset of points, given a constraint on the sum of squared Euclidean distances between them. We consider the computational complexity of both problems and propose exact dynamic programming algorithms in the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, these algorithms have a pseudo-polynomial time complexity. We also develop an FPTAS for the special case of the first problem, where the dimension of the Euclidean space is bounded by a constant.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10472-021-09773-z", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.8728495", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1043955", 
            "issn": [
              "1012-2443", 
              "1573-7470"
            ], 
            "name": "Annals of Mathematics and Artificial Intelligence", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "squared Euclidean distance", 
          "Euclidean distance", 
          "pseudo-polynomial time complexity", 
          "exact dynamic programming algorithm", 
          "dynamic programming algorithm", 
          "first problem", 
          "time complexity", 
          "computational complexity", 
          "programming algorithm", 
          "input data", 
          "minimum cardinality subset", 
          "set of points", 
          "Euclidean space", 
          "algorithm", 
          "second problem", 
          "complexity", 
          "diverse points", 
          "related problems", 
          "size M", 
          "diverse subset", 
          "FPTAS", 
          "space", 
          "special case", 
          "constraints", 
          "subset", 
          "set", 
          "point", 
          "distance", 
          "problem", 
          "sum", 
          "data", 
          "dimensions", 
          "cases", 
          "respect", 
          "constants", 
          "paper", 
          "cardinality subset", 
          "integer input data"
        ], 
        "name": "Selecting a subset of diverse points based on the squared euclidean distance", 
        "pagination": "1-13", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1141302469"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10472-021-09773-z"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10472-021-09773-z", 
          "https://app.dimensions.ai/details/publication/pub.1141302469"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T19:03", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_902.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10472-021-09773-z"
      }
    ]
     

    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/s10472-021-09773-z'

    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/s10472-021-09773-z'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09773-z'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09773-z'


     

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

    152 TRIPLES      22 PREDICATES      70 URIs      53 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10472-021-09773-z schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N79f501dbe77747ae849c60d319643b18
    4 schema:citation sg:pub.10.1007/978-3-030-04693-4_1
    5 sg:pub.10.1007/978-3-030-22629-9_38
    6 sg:pub.10.1007/978-3-030-53552-0_6
    7 sg:pub.10.1007/s10100-009-0093-3
    8 sg:pub.10.1134/s0005117912020129
    9 sg:pub.10.1134/s1990478911030069
    10 sg:pub.10.1134/s1990478912030131
    11 sg:pub.10.1134/s1990478914030041
    12 sg:pub.10.1134/s199047891604013x
    13 schema:datePublished 2021-09-22
    14 schema:datePublishedReg 2021-09-22
    15 schema:description In this paper we consider two closely related problems of selecting a diverse subset of points with respect to squared Euclidean distance. Given a set of points in Euclidean space, the first problem is to find a subset of a specified size M maximizing the sum of squared Euclidean distances between the chosen points. The second problem asks for a minimum cardinality subset of points, given a constraint on the sum of squared Euclidean distances between them. We consider the computational complexity of both problems and propose exact dynamic programming algorithms in the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, these algorithms have a pseudo-polynomial time complexity. We also develop an FPTAS for the special case of the first problem, where the dimension of the Euclidean space is bounded by a constant.
    16 schema:genre article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf sg:journal.1043955
    20 schema:keywords Euclidean distance
    21 Euclidean space
    22 FPTAS
    23 algorithm
    24 cardinality subset
    25 cases
    26 complexity
    27 computational complexity
    28 constants
    29 constraints
    30 data
    31 dimensions
    32 distance
    33 diverse points
    34 diverse subset
    35 dynamic programming algorithm
    36 exact dynamic programming algorithm
    37 first problem
    38 input data
    39 integer input data
    40 minimum cardinality subset
    41 paper
    42 point
    43 problem
    44 programming algorithm
    45 pseudo-polynomial time complexity
    46 related problems
    47 respect
    48 second problem
    49 set
    50 set of points
    51 size M
    52 space
    53 special case
    54 squared Euclidean distance
    55 subset
    56 sum
    57 time complexity
    58 schema:name Selecting a subset of diverse points based on the squared euclidean distance
    59 schema:pagination 1-13
    60 schema:productId Nc7364d7fcd0b4317ba808a9b5c07dbd9
    61 Nfd4689830d9d45fda9aafaaaedd646fa
    62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1141302469
    63 https://doi.org/10.1007/s10472-021-09773-z
    64 schema:sdDatePublished 2022-01-01T19:03
    65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    66 schema:sdPublisher Ne6bcfb8c18314481a49fb9602becf11f
    67 schema:url https://doi.org/10.1007/s10472-021-09773-z
    68 sgo:license sg:explorer/license/
    69 sgo:sdDataset articles
    70 rdf:type schema:ScholarlyArticle
    71 N79f501dbe77747ae849c60d319643b18 rdf:first sg:person.015645525051.36
    72 rdf:rest Nb1d92d3a2b7f4cf1bf2109e154296b6a
    73 N9ee10f65758a472ca4cd5489e033fa19 rdf:first sg:person.016544210352.26
    74 rdf:rest rdf:nil
    75 Nb1d92d3a2b7f4cf1bf2109e154296b6a rdf:first sg:person.012666512667.93
    76 rdf:rest Nd681418eeeae4e0fbb287af1e2d11f34
    77 Nc7364d7fcd0b4317ba808a9b5c07dbd9 schema:name doi
    78 schema:value 10.1007/s10472-021-09773-z
    79 rdf:type schema:PropertyValue
    80 Nd681418eeeae4e0fbb287af1e2d11f34 rdf:first sg:person.015744710763.41
    81 rdf:rest N9ee10f65758a472ca4cd5489e033fa19
    82 Ne6bcfb8c18314481a49fb9602becf11f schema:name Springer Nature - SN SciGraph project
    83 rdf:type schema:Organization
    84 Nfd4689830d9d45fda9aafaaaedd646fa schema:name dimensions_id
    85 schema:value pub.1141302469
    86 rdf:type schema:PropertyValue
    87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Information and Computing Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Computation Theory and Mathematics
    92 rdf:type schema:DefinedTerm
    93 sg:grant.8728495 http://pending.schema.org/fundedItem sg:pub.10.1007/s10472-021-09773-z
    94 rdf:type schema:MonetaryGrant
    95 sg:journal.1043955 schema:issn 1012-2443
    96 1573-7470
    97 schema:name Annals of Mathematics and Artificial Intelligence
    98 schema:publisher Springer Nature
    99 rdf:type schema:Periodical
    100 sg:person.012666512667.93 schema:affiliation grid-institutes:grid.426295.e
    101 schema:familyName Kel’manov
    102 schema:givenName Alexander V.
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012666512667.93
    104 rdf:type schema:Person
    105 sg:person.015645525051.36 schema:affiliation grid-institutes:grid.426295.e
    106 schema:familyName Eremeev
    107 schema:givenName Anton V.
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015645525051.36
    109 rdf:type schema:Person
    110 sg:person.015744710763.41 schema:affiliation grid-institutes:grid.426549.8
    111 schema:familyName Kovalyov
    112 schema:givenName Mikhail Y.
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015744710763.41
    114 rdf:type schema:Person
    115 sg:person.016544210352.26 schema:affiliation grid-institutes:grid.426295.e
    116 schema:familyName Pyatkin
    117 schema:givenName Artem V.
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016544210352.26
    119 rdf:type schema:Person
    120 sg:pub.10.1007/978-3-030-04693-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110287584
    121 https://doi.org/10.1007/978-3-030-04693-4_1
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-030-22629-9_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1117044082
    124 https://doi.org/10.1007/978-3-030-22629-9_38
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-030-53552-0_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1129443842
    127 https://doi.org/10.1007/978-3-030-53552-0_6
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/s10100-009-0093-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011157397
    130 https://doi.org/10.1007/s10100-009-0093-3
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1134/s0005117912020129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048959771
    133 https://doi.org/10.1134/s0005117912020129
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1134/s1990478911030069 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008382823
    136 https://doi.org/10.1134/s1990478911030069
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1134/s1990478912030131 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036516748
    139 https://doi.org/10.1134/s1990478912030131
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1134/s1990478914030041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045548031
    142 https://doi.org/10.1134/s1990478914030041
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1134/s199047891604013x schema:sameAs https://app.dimensions.ai/details/publication/pub.1042531934
    145 https://doi.org/10.1134/s199047891604013x
    146 rdf:type schema:CreativeWork
    147 grid-institutes:grid.426295.e schema:alternateName Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia
    148 schema:name Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia
    149 rdf:type schema:Organization
    150 grid-institutes:grid.426549.8 schema:alternateName United Institute of Informatics Problems, Minsk, Belarus
    151 schema:name United Institute of Informatics Problems, Minsk, Belarus
    152 rdf:type schema:Organization
     




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


    ...