Using Relaxations in Maximum Density Still Life View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Geoffrey Chu , Peter J. Stuckey , Maria Garcia de la Banda

ABSTRACT

The Maximum Density Sill-Life Problem is to fill an n ×n board of cells with the maximum number of live cells so that the board is stable under the rules of Conway’s Game of Life. We reformulate the problem into one of minimising “wastage” rather than maximising the number of live cells. This reformulation allows us to compute strong upper bounds on the number of live cells. By combining this reformulation with several relaxation techniques, as well as exploiting symmetries via caching, we are able to find close to optimal solutions up to size n = 100, and optimal solutions for instances as large as n = 69. The best previous method could only find optimal solutions up to n = 20. More... »

PAGES

258-273

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-04244-7_22

DOI

http://dx.doi.org/10.1007/978-3-642-04244-7_22

DIMENSIONS

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


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/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Cardiorespiratory Medicine and Haematology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1008.9", 
          "name": [
            "NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chu", 
        "givenName": "Geoffrey", 
        "id": "sg:person.013732020721.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732020721.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1008.9", 
          "name": [
            "NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stuckey", 
        "givenName": "Peter J.", 
        "id": "sg:person.012243374043.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Information Technology, Monash University, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Faculty of Information Technology, Monash University, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "de la Banda", 
        "givenName": "Maria Garcia", 
        "id": "sg:person.016350443307.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "The Maximum Density Sill-Life Problem is to fill an n \u00d7n board of cells with the maximum number of live cells so that the board is stable under the rules of Conway\u2019s Game of Life. We reformulate the problem into one of minimising \u201cwastage\u201d rather than maximising the number of live cells. This reformulation allows us to compute strong upper bounds on the number of live cells. By combining this reformulation with several relaxation techniques, as well as exploiting symmetries via caching, we are able to find close to optimal solutions up to size n\u2009=\u2009100, and optimal solutions for instances as large as n\u2009=\u200969. The best previous method could only find optimal solutions up to n\u2009=\u200920.", 
    "editor": [
      {
        "familyName": "Gent", 
        "givenName": "Ian P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-04244-7_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-04243-0", 
        "978-3-642-04244-7"
      ], 
      "name": "Principles and Practice of Constraint Programming - CP 2009", 
      "type": "Book"
    }, 
    "keywords": [
      "optimal solution", 
      "strong upper bounds", 
      "upper bounds", 
      "size n", 
      "relaxation techniques", 
      "reformulation", 
      "maximum number", 
      "previous methods", 
      "solution", 
      "Conway\u2019s Game", 
      "problem", 
      "bounds", 
      "symmetry", 
      "number", 
      "maximum density", 
      "relaxation", 
      "game", 
      "instances", 
      "rules", 
      "technique", 
      "density", 
      "caching", 
      "board", 
      "wastage", 
      "cells", 
      "live cells", 
      "life", 
      "method"
    ], 
    "name": "Using Relaxations in Maximum Density Still Life", 
    "pagination": "258-273", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001581529"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-04244-7_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-04244-7_22", 
      "https://app.dimensions.ai/details/publication/pub.1001581529"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:48", 
    "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_45.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-04244-7_22"
  }
]
 

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-04244-7_22'

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-04244-7_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-04244-7_22'

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-04244-7_22'


 

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

105 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-04244-7_22 schema:about anzsrc-for:11
2 anzsrc-for:1102
3 schema:author N740d09179f6042f89b759d79c09be016
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description The Maximum Density Sill-Life Problem is to fill an n ×n board of cells with the maximum number of live cells so that the board is stable under the rules of Conway’s Game of Life. We reformulate the problem into one of minimising “wastage” rather than maximising the number of live cells. This reformulation allows us to compute strong upper bounds on the number of live cells. By combining this reformulation with several relaxation techniques, as well as exploiting symmetries via caching, we are able to find close to optimal solutions up to size n = 100, and optimal solutions for instances as large as n = 69. The best previous method could only find optimal solutions up to n = 20.
7 schema:editor N8af093716db44d7596810ba0744232d3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N039c4d8f38e3489f9b6eaa0c8a495e13
12 schema:keywords Conway’s Game
13 board
14 bounds
15 caching
16 cells
17 density
18 game
19 instances
20 life
21 live cells
22 maximum density
23 maximum number
24 method
25 number
26 optimal solution
27 previous methods
28 problem
29 reformulation
30 relaxation
31 relaxation techniques
32 rules
33 size n
34 solution
35 strong upper bounds
36 symmetry
37 technique
38 upper bounds
39 wastage
40 schema:name Using Relaxations in Maximum Density Still Life
41 schema:pagination 258-273
42 schema:productId Na5122447b45a42d899f02451dcc552ad
43 Nc2043d1c1f614faaa7f63111b0e2725f
44 schema:publisher N6f2fd3d5fa9c4f63a356cf65092ce4f8
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001581529
46 https://doi.org/10.1007/978-3-642-04244-7_22
47 schema:sdDatePublished 2022-05-20T07:48
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N599956b606d44623939e16d29b52bf9d
50 schema:url https://doi.org/10.1007/978-3-642-04244-7_22
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N039c4d8f38e3489f9b6eaa0c8a495e13 schema:isbn 978-3-642-04243-0
55 978-3-642-04244-7
56 schema:name Principles and Practice of Constraint Programming - CP 2009
57 rdf:type schema:Book
58 N12ae889c124c4466bdbdd8954a4797c3 schema:familyName Gent
59 schema:givenName Ian P.
60 rdf:type schema:Person
61 N44274e312a9244228f5bba2ace497c06 rdf:first sg:person.016350443307.93
62 rdf:rest rdf:nil
63 N599956b606d44623939e16d29b52bf9d schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N6f2fd3d5fa9c4f63a356cf65092ce4f8 schema:name Springer Nature
66 rdf:type schema:Organisation
67 N740d09179f6042f89b759d79c09be016 rdf:first sg:person.013732020721.53
68 rdf:rest Nff92dd5647424d6ab6c39c71c4af73c4
69 N8af093716db44d7596810ba0744232d3 rdf:first N12ae889c124c4466bdbdd8954a4797c3
70 rdf:rest rdf:nil
71 Na5122447b45a42d899f02451dcc552ad schema:name dimensions_id
72 schema:value pub.1001581529
73 rdf:type schema:PropertyValue
74 Nc2043d1c1f614faaa7f63111b0e2725f schema:name doi
75 schema:value 10.1007/978-3-642-04244-7_22
76 rdf:type schema:PropertyValue
77 Nff92dd5647424d6ab6c39c71c4af73c4 rdf:first sg:person.012243374043.93
78 rdf:rest N44274e312a9244228f5bba2ace497c06
79 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
80 schema:name Medical and Health Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:1102 schema:inDefinedTermSet anzsrc-for:
83 schema:name Cardiorespiratory Medicine and Haematology
84 rdf:type schema:DefinedTerm
85 sg:person.012243374043.93 schema:affiliation grid-institutes:grid.1008.9
86 schema:familyName Stuckey
87 schema:givenName Peter J.
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93
89 rdf:type schema:Person
90 sg:person.013732020721.53 schema:affiliation grid-institutes:grid.1008.9
91 schema:familyName Chu
92 schema:givenName Geoffrey
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732020721.53
94 rdf:type schema:Person
95 sg:person.016350443307.93 schema:affiliation grid-institutes:grid.1002.3
96 schema:familyName de la Banda
97 schema:givenName Maria Garcia
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93
99 rdf:type schema:Person
100 grid-institutes:grid.1002.3 schema:alternateName Faculty of Information Technology, Monash University, Australia
101 schema:name Faculty of Information Technology, Monash University, Australia
102 rdf:type schema:Organization
103 grid-institutes:grid.1008.9 schema:alternateName NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia
104 schema:name NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia
105 rdf:type schema:Organization
 




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


...