Approximately Dominating Representatives View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Vladlen Koltun , Christos H. Papadimitriou

ABSTRACT

We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called approximately dominating representatives or ADRs. The ADRs of a multidimensional point set consist of a few points guaranteed to contain an approximate optimum of any monotone Lipschitz continuous combining function of the dimensions. ADRs can be computed by appropriately post-processing Pareto, or “skyline,” queries [14,1]. We show that the problem of minimizing the number of points returned, for a user-specified desired approximation, can be solved in polynomial time in two dimensions; for three and more it is NP-hard but has a polynomial-time logarithmic approximation. Finally, we present a polynomial-time, constant factor approximation algorithm for three dimensions. More... »

PAGES

204-214

Book

TITLE

Database Theory - ICDT 2005

ISBN

978-3-540-24288-8
978-3-540-30570-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30570-5_14

DOI

http://dx.doi.org/10.1007/978-3-540-30570-5_14

DIMENSIONS

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


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": "Computer Science Division, University of California, 94720-1776, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California, 94720-1776, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Koltun", 
        "givenName": "Vladlen", 
        "id": "sg:person.015565367417.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015565367417.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California, 94720-1776, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California, 94720-1776, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called approximately dominating representatives or ADRs. The ADRs of a multidimensional point set consist of a few points guaranteed to contain an approximate optimum of any monotone Lipschitz continuous combining function of the dimensions. ADRs can be computed by appropriately post-processing Pareto, or \u201cskyline,\u201d queries [14,1]. We show that the problem of minimizing the number of points returned, for a user-specified desired approximation, can be solved in polynomial time in two dimensions; for three and more it is NP-hard but has a polynomial-time logarithmic approximation. Finally, we present a polynomial-time, constant factor approximation algorithm for three dimensions.", 
    "editor": [
      {
        "familyName": "Eiter", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Libkin", 
        "givenName": "Leonid", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30570-5_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24288-8", 
        "978-3-540-30570-5"
      ], 
      "name": "Database Theory - ICDT 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "constant factor approximation algorithm", 
      "factor approximation algorithm", 
      "fuzzy queries", 
      "algorithmic standpoint", 
      "approximation algorithm", 
      "polynomial time", 
      "multidimensional points", 
      "queries", 
      "approximate optimum", 
      "number of points", 
      "skyline", 
      "algorithm", 
      "NP", 
      "Pareto", 
      "point", 
      "optimum", 
      "novel form", 
      "approximation", 
      "dimensions", 
      "logarithmic approximation", 
      "consist", 
      "number", 
      "time", 
      "function", 
      "standpoint", 
      "representatives", 
      "Lipschitz", 
      "form", 
      "ADR", 
      "problem", 
      "monotone Lipschitz", 
      "post-processing Pareto", 
      "polynomial-time logarithmic approximation"
    ], 
    "name": "Approximately Dominating Representatives", 
    "pagination": "204-214", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029456772"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30570-5_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30570-5_14", 
      "https://app.dimensions.ai/details/publication/pub.1029456772"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_263.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30570-5_14"
  }
]
 

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-540-30570-5_14'

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-540-30570-5_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30570-5_14'

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-540-30570-5_14'


 

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

105 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30570-5_14 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nca92da2c32914779bf7c0431d5fb060c
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called approximately dominating representatives or ADRs. The ADRs of a multidimensional point set consist of a few points guaranteed to contain an approximate optimum of any monotone Lipschitz continuous combining function of the dimensions. ADRs can be computed by appropriately post-processing Pareto, or “skyline,” queries [14,1]. We show that the problem of minimizing the number of points returned, for a user-specified desired approximation, can be solved in polynomial time in two dimensions; for three and more it is NP-hard but has a polynomial-time logarithmic approximation. Finally, we present a polynomial-time, constant factor approximation algorithm for three dimensions.
7 schema:editor Naf0b38d6bfca4cb5a593198a0726dd27
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5a2ef136cfc74cc9914795f0e6a0231f
12 schema:keywords ADR
13 Lipschitz
14 NP
15 Pareto
16 algorithm
17 algorithmic standpoint
18 approximate optimum
19 approximation
20 approximation algorithm
21 consist
22 constant factor approximation algorithm
23 dimensions
24 factor approximation algorithm
25 form
26 function
27 fuzzy queries
28 logarithmic approximation
29 monotone Lipschitz
30 multidimensional points
31 novel form
32 number
33 number of points
34 optimum
35 point
36 polynomial time
37 polynomial-time logarithmic approximation
38 post-processing Pareto
39 problem
40 queries
41 representatives
42 skyline
43 standpoint
44 time
45 schema:name Approximately Dominating Representatives
46 schema:pagination 204-214
47 schema:productId N28ad0658a3064240b626e681f7c1a549
48 N69444704c0f345a986d5b5b89c19d2cf
49 schema:publisher N750feb025a94440b813fbea6c409ee17
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029456772
51 https://doi.org/10.1007/978-3-540-30570-5_14
52 schema:sdDatePublished 2021-12-01T20:02
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N09094349580b478c82c5394292dcc35c
55 schema:url https://doi.org/10.1007/978-3-540-30570-5_14
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N09094349580b478c82c5394292dcc35c schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 N0c320d551006439eb7052bb436df8c2a rdf:first N2750ab9d18024cd5b45cb2897cf4178d
62 rdf:rest rdf:nil
63 N2750ab9d18024cd5b45cb2897cf4178d schema:familyName Libkin
64 schema:givenName Leonid
65 rdf:type schema:Person
66 N28ad0658a3064240b626e681f7c1a549 schema:name doi
67 schema:value 10.1007/978-3-540-30570-5_14
68 rdf:type schema:PropertyValue
69 N5a2ef136cfc74cc9914795f0e6a0231f schema:isbn 978-3-540-24288-8
70 978-3-540-30570-5
71 schema:name Database Theory - ICDT 2005
72 rdf:type schema:Book
73 N69444704c0f345a986d5b5b89c19d2cf schema:name dimensions_id
74 schema:value pub.1029456772
75 rdf:type schema:PropertyValue
76 N750feb025a94440b813fbea6c409ee17 schema:name Springer Nature
77 rdf:type schema:Organisation
78 Nae10b32f90334dbf9c6af620a734b189 schema:familyName Eiter
79 schema:givenName Thomas
80 rdf:type schema:Person
81 Naf0b38d6bfca4cb5a593198a0726dd27 rdf:first Nae10b32f90334dbf9c6af620a734b189
82 rdf:rest N0c320d551006439eb7052bb436df8c2a
83 Nca92da2c32914779bf7c0431d5fb060c rdf:first sg:person.015565367417.08
84 rdf:rest Ne01bf9d5dc0e46918fe680c0501e9a63
85 Ne01bf9d5dc0e46918fe680c0501e9a63 rdf:first sg:person.013233165465.63
86 rdf:rest rdf:nil
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:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
94 schema:familyName Papadimitriou
95 schema:givenName Christos H.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
97 rdf:type schema:Person
98 sg:person.015565367417.08 schema:affiliation grid-institutes:grid.47840.3f
99 schema:familyName Koltun
100 schema:givenName Vladlen
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015565367417.08
102 rdf:type schema:Person
103 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California, 94720-1776, Berkeley, CA, USA
104 schema:name Computer Science Division, University of California, 94720-1776, Berkeley, CA, USA
105 rdf:type schema:Organization
 




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


...