An Improved Randomized Approximation Algorithm for Maximum Triangle Packing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008-01-01

AUTHORS

Zhi-Zhong Chen , Ruka Tanahashi , Lusheng Wang

ABSTRACT

This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm and claimed that it achieves an expected ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{89}{169}(1 - \epsilon)$\end{document} for any constant ε> 0. However, their analysis was flawed. We present a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio very close to their claimed expected ratio. More... »

PAGES

97-108

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-68880-8_11

DOI

http://dx.doi.org/10.1007/978-3-540-68880-8_11

DIMENSIONS

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


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": "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tanahashi", 
        "givenName": "Ruka", 
        "id": "sg:person.014101003752.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014101003752.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm and claimed that it achieves an expected ratio of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\frac{89}{169}(1 - \\epsilon)$\\end{document} for any constant \u03b5>\u20090. However, their analysis was flawed. We present a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio very close to their claimed expected ratio.", 
    "editor": [
      {
        "familyName": "Fleischer", 
        "givenName": "Rudolf", 
        "type": "Person"
      }, 
      {
        "familyName": "Xu", 
        "givenName": "Jinhui", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-68880-8_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-68865-5", 
        "978-3-540-68880-8"
      ], 
      "name": "Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "ratio", 
      "paper", 
      "packing problem", 
      "problem", 
      "Rubinstein", 
      "approximation algorithm", 
      "algorithm", 
      "analysis", 
      "packing", 
      "maximum triangle packing problem", 
      "triangle packing problem", 
      "Hassin", 
      "polynomial-time approximation algorithm", 
      "randomized approximation algorithm", 
      "Maximum Triangle Packing", 
      "triangle packing"
    ], 
    "name": "An Improved Randomized Approximation Algorithm for Maximum Triangle Packing", 
    "pagination": "97-108", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037798593"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-68880-8_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-68880-8_11", 
      "https://app.dimensions.ai/details/publication/pub.1037798593"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_180.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-68880-8_11"
  }
]
 

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-68880-8_11'

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-68880-8_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-68880-8_11'

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-68880-8_11'


 

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

98 TRIPLES      23 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-68880-8_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na9dfc60c01e24b0a80a639b4fe53fe7b
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm and claimed that it achieves an expected ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{89}{169}(1 - \epsilon)$\end{document} for any constant ε> 0. However, their analysis was flawed. We present a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio very close to their claimed expected ratio.
7 schema:editor N45a4554bdc524c5c9b1a67a397e22c25
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N6ad37a33b9e142c2b8f77a32c6e47b80
12 schema:keywords Hassin
13 Maximum Triangle Packing
14 Rubinstein
15 algorithm
16 analysis
17 approximation algorithm
18 maximum triangle packing problem
19 packing
20 packing problem
21 paper
22 polynomial-time approximation algorithm
23 problem
24 randomized approximation algorithm
25 ratio
26 triangle packing
27 triangle packing problem
28 schema:name An Improved Randomized Approximation Algorithm for Maximum Triangle Packing
29 schema:pagination 97-108
30 schema:productId N2118ce894eec495e88c207ff6eca8017
31 N3513d7401a20489f8cf5f1196c944802
32 schema:publisher N54a604823c344500918f4c4ed6ea87ff
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037798593
34 https://doi.org/10.1007/978-3-540-68880-8_11
35 schema:sdDatePublished 2022-05-20T07:42
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher Nd72c7dc0c34f45c78d42e9712cd4cf47
38 schema:url https://doi.org/10.1007/978-3-540-68880-8_11
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N11e5adacc0124c998a72bbe7daec1226 rdf:first sg:person.01105113721.52
43 rdf:rest rdf:nil
44 N1df445f666f84c75867802e7df166eb6 schema:familyName Fleischer
45 schema:givenName Rudolf
46 rdf:type schema:Person
47 N2118ce894eec495e88c207ff6eca8017 schema:name doi
48 schema:value 10.1007/978-3-540-68880-8_11
49 rdf:type schema:PropertyValue
50 N3513d7401a20489f8cf5f1196c944802 schema:name dimensions_id
51 schema:value pub.1037798593
52 rdf:type schema:PropertyValue
53 N45a4554bdc524c5c9b1a67a397e22c25 rdf:first N1df445f666f84c75867802e7df166eb6
54 rdf:rest Ne511a82f3272460098e0fad152083ead
55 N4a018f9e121c41dd8b1373f49f2870c8 rdf:first sg:person.014101003752.39
56 rdf:rest N11e5adacc0124c998a72bbe7daec1226
57 N54a604823c344500918f4c4ed6ea87ff schema:name Springer Nature
58 rdf:type schema:Organisation
59 N6ad37a33b9e142c2b8f77a32c6e47b80 schema:isbn 978-3-540-68865-5
60 978-3-540-68880-8
61 schema:name Algorithmic Aspects in Information and Management
62 rdf:type schema:Book
63 N7cd0a7823a9c427caed1c1a347f59f97 schema:familyName Xu
64 schema:givenName Jinhui
65 rdf:type schema:Person
66 Na9dfc60c01e24b0a80a639b4fe53fe7b rdf:first sg:person.015654265661.98
67 rdf:rest N4a018f9e121c41dd8b1373f49f2870c8
68 Nd72c7dc0c34f45c78d42e9712cd4cf47 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Ne511a82f3272460098e0fad152083ead rdf:first N7cd0a7823a9c427caed1c1a347f59f97
71 rdf:rest rdf:nil
72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information and Computing Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
76 schema:name Computation Theory and Mathematics
77 rdf:type schema:DefinedTerm
78 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
79 schema:familyName Wang
80 schema:givenName Lusheng
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
82 rdf:type schema:Person
83 sg:person.014101003752.39 schema:affiliation grid-institutes:grid.412773.4
84 schema:familyName Tanahashi
85 schema:givenName Ruka
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014101003752.39
87 rdf:type schema:Person
88 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
89 schema:familyName Chen
90 schema:givenName Zhi-Zhong
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
92 rdf:type schema:Person
93 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
94 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
95 rdf:type schema:Organization
96 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
97 schema:name Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
98 rdf:type schema:Organization
 




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


...