An optimal approximation algorithm for the rectilinearm-center problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-06

AUTHORS

M. T. Ko, R. C. T. Lee, J. S. Chang

ABSTRACT

Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio ɛ < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed. More... »

PAGES

341

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01840393

DOI

http://dx.doi.org/10.1007/bf01840393

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ko", 
        "givenName": "M. T.", 
        "id": "sg:person.015227651231.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015227651231.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The Academia Sinica, Taipei, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "National Tsing Hua University, Hsinchu, Taiwan", 
            "The Academia Sinica, Taipei, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "R. C. T.", 
        "id": "sg:person.07540250215.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "J. S.", 
        "id": "sg:person.012045506405.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012045506405.60"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1990-06", 
    "datePublishedReg": "1990-06-01", 
    "description": "Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio \u025b < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01840393", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "keywords": [
      "approximation algorithm", 
      "polynomial-time approximation algorithm", 
      "polynomial-time algorithm", 
      "optimal approximation algorithm", 
      "error ratio", 
      "algorithm", 
      "ofn points", 
      "NP", 
      "point", 
      "squares", 
      "problem", 
      "side length", 
      "plane", 
      "ratio", 
      "length", 
      "paper", 
      "rectilinearm-center problem", 
      "findn rectilinear squares", 
      "rectilinear squares", 
      "maximum side length"
    ], 
    "name": "An optimal approximation algorithm for the rectilinearm-center problem", 
    "pagination": "341", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053618684"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01840393"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01840393", 
      "https://app.dimensions.ai/details/publication/pub.1053618684"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:08", 
    "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/article/article_245.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01840393"
  }
]
 

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/bf01840393'

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/bf01840393'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01840393'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01840393'


 

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

96 TRIPLES      21 PREDICATES      46 URIs      38 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01840393 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nd819593dc3e04e16ba6609f1f18c929f
4 schema:datePublished 1990-06
5 schema:datePublishedReg 1990-06-01
6 schema:description Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio ɛ < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N3b14f2e98cea4bc998e85f2a0ccff9ff
11 N538c617338114ffda8ec884ffedaaff2
12 sg:journal.1047644
13 schema:keywords NP
14 algorithm
15 approximation algorithm
16 error ratio
17 findn rectilinear squares
18 length
19 maximum side length
20 ofn points
21 optimal approximation algorithm
22 paper
23 plane
24 point
25 polynomial-time algorithm
26 polynomial-time approximation algorithm
27 problem
28 ratio
29 rectilinear squares
30 rectilinearm-center problem
31 side length
32 squares
33 schema:name An optimal approximation algorithm for the rectilinearm-center problem
34 schema:pagination 341
35 schema:productId N0f59f015d9c24bb78141319e55390507
36 N5bd56da29fa84538b10cbaa033ff6603
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053618684
38 https://doi.org/10.1007/bf01840393
39 schema:sdDatePublished 2021-12-01T19:08
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Ncb56e724684b44b6b38a3d49ae23243e
42 schema:url https://doi.org/10.1007/bf01840393
43 sgo:license sg:explorer/license/
44 sgo:sdDataset articles
45 rdf:type schema:ScholarlyArticle
46 N0a03d145a8e34d90aa468ac03af3534f rdf:first sg:person.07540250215.50
47 rdf:rest N42696f3e9eae413e8d53cf19d0d910e6
48 N0f59f015d9c24bb78141319e55390507 schema:name doi
49 schema:value 10.1007/bf01840393
50 rdf:type schema:PropertyValue
51 N3b14f2e98cea4bc998e85f2a0ccff9ff schema:volumeNumber 5
52 rdf:type schema:PublicationVolume
53 N42696f3e9eae413e8d53cf19d0d910e6 rdf:first sg:person.012045506405.60
54 rdf:rest rdf:nil
55 N538c617338114ffda8ec884ffedaaff2 schema:issueNumber 1-4
56 rdf:type schema:PublicationIssue
57 N5bd56da29fa84538b10cbaa033ff6603 schema:name dimensions_id
58 schema:value pub.1053618684
59 rdf:type schema:PropertyValue
60 Ncb56e724684b44b6b38a3d49ae23243e schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Nd819593dc3e04e16ba6609f1f18c929f rdf:first sg:person.015227651231.73
63 rdf:rest N0a03d145a8e34d90aa468ac03af3534f
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
68 schema:name Numerical and Computational Mathematics
69 rdf:type schema:DefinedTerm
70 sg:journal.1047644 schema:issn 0178-4617
71 1432-0541
72 schema:name Algorithmica
73 schema:publisher Springer Nature
74 rdf:type schema:Periodical
75 sg:person.012045506405.60 schema:affiliation grid-institutes:grid.38348.34
76 schema:familyName Chang
77 schema:givenName J. S.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012045506405.60
79 rdf:type schema:Person
80 sg:person.015227651231.73 schema:affiliation grid-institutes:grid.38348.34
81 schema:familyName Ko
82 schema:givenName M. T.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015227651231.73
84 rdf:type schema:Person
85 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.28665.3f
86 schema:familyName Lee
87 schema:givenName R. C. T.
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
89 rdf:type schema:Person
90 grid-institutes:grid.28665.3f schema:alternateName The Academia Sinica, Taipei, Taiwan, Republic of China
91 schema:name National Tsing Hua University, Hsinchu, Taiwan
92 The Academia Sinica, Taipei, Taiwan, Republic of China
93 rdf:type schema:Organization
94 grid-institutes:grid.38348.34 schema:alternateName Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
95 schema:name Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
96 rdf:type schema:Organization
 




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


...