New local search approximation techniques for maximum generalized satisfiability problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1994

AUTHORS

Paola Alimonti

ABSTRACT

We investigate the relationship beetween the classes MAX-NP and GLO by studying the Maximum Generalized Satisfiability problem, which is in the former class. We present a (2−B)-approximate greedy heuristic for this problem and show that no local search c-approximate algorithm exists, based on an h-bounded neighborhood and on the number of satisfied clauses as objective function. This implies that, with the standard definition of local search, MAX-NP is not contained in GLO. We then show that, by introducing a different local search technique, that is using a different neighborhood structure for B = 2 and an auxiliary objective function in the general case, a local search (2−B)-approximate algorithms can be found for this problem. The latter result, that holds in the general case, suggests how to modify the definition of local search in order to extend the power of this general approch. In the same way, we can enlarge the class GLO of problems that can be efficiently approximated by local search techniques. More... »

PAGES

40-53

Book

TITLE

Algorithms and Complexity

ISBN

978-3-540-57811-6
978-3-540-48337-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57811-0_5

DOI

http://dx.doi.org/10.1007/3-540-57811-0_5

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, 00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alimonti", 
        "givenName": "Paola", 
        "id": "sg:person.015632520461.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "We investigate the relationship beetween the classes MAX-NP and GLO by studying the Maximum Generalized Satisfiability problem, which is in the former class. We present a (2\u2212B)-approximate greedy heuristic for this problem and show that no local search c-approximate algorithm exists, based on an h-bounded neighborhood and on the number of satisfied clauses as objective function. This implies that, with the standard definition of local search, MAX-NP is not contained in GLO. We then show that, by introducing a different local search technique, that is using a different neighborhood structure for B = 2 and an auxiliary objective function in the general case, a local search (2\u2212B)-approximate algorithms can be found for this problem. The latter result, that holds in the general case, suggests how to modify the definition of local search in order to extend the power of this general approch. In the same way, we can enlarge the class GLO of problems that can be efficiently approximated by local search techniques.", 
    "editor": [
      {
        "familyName": "Bonuccelli", 
        "givenName": "M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Crescenzi", 
        "givenName": "P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Petreschi", 
        "givenName": "R.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57811-0_5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57811-6", 
        "978-3-540-48337-3"
      ], 
      "name": "Algorithms and Complexity", 
      "type": "Book"
    }, 
    "name": "New local search approximation techniques for maximum generalized satisfiability problems", 
    "pagination": "40-53", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57811-0_5"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e5aedb1030693e3d1b2211b7fa8fed83ca7e4ade28e3c7e9de3af84c442ed46c"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048213566"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57811-0_5", 
      "https://app.dimensions.ai/details/publication/pub.1048213566"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T22:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000083.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-57811-0_5"
  }
]
 

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/3-540-57811-0_5'

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/3-540-57811-0_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57811-0_5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57811-0_5'


 

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

75 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57811-0_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N34369dc9bc90431686e96b0665f37e55
4 schema:datePublished 1994
5 schema:datePublishedReg 1994-01-01
6 schema:description We investigate the relationship beetween the classes MAX-NP and GLO by studying the Maximum Generalized Satisfiability problem, which is in the former class. We present a (2−B)-approximate greedy heuristic for this problem and show that no local search c-approximate algorithm exists, based on an h-bounded neighborhood and on the number of satisfied clauses as objective function. This implies that, with the standard definition of local search, MAX-NP is not contained in GLO. We then show that, by introducing a different local search technique, that is using a different neighborhood structure for B = 2 and an auxiliary objective function in the general case, a local search (2−B)-approximate algorithms can be found for this problem. The latter result, that holds in the general case, suggests how to modify the definition of local search in order to extend the power of this general approch. In the same way, we can enlarge the class GLO of problems that can be efficiently approximated by local search techniques.
7 schema:editor N4f7f73d82c8e4e78b3630d920e7b5240
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N97d374da67d442d38f6368a5de7aa6a0
12 schema:name New local search approximation techniques for maximum generalized satisfiability problems
13 schema:pagination 40-53
14 schema:productId N06f62c53076046dcb47de71f261cca79
15 N1ca1399b27bb4d1b80f959eef734dabe
16 N5148d07748d84fe7886d049f74587bac
17 schema:publisher N63957b0392b449179ca198e6ab062166
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048213566
19 https://doi.org/10.1007/3-540-57811-0_5
20 schema:sdDatePublished 2019-04-15T22:45
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Ned52b03f769743289794776dcf3a5a2f
23 schema:url http://link.springer.com/10.1007/3-540-57811-0_5
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N06f62c53076046dcb47de71f261cca79 schema:name doi
28 schema:value 10.1007/3-540-57811-0_5
29 rdf:type schema:PropertyValue
30 N1ca1399b27bb4d1b80f959eef734dabe schema:name readcube_id
31 schema:value e5aedb1030693e3d1b2211b7fa8fed83ca7e4ade28e3c7e9de3af84c442ed46c
32 rdf:type schema:PropertyValue
33 N34369dc9bc90431686e96b0665f37e55 rdf:first sg:person.015632520461.69
34 rdf:rest rdf:nil
35 N4f7f73d82c8e4e78b3630d920e7b5240 rdf:first N823f8b4e80644d9984f37165408c1894
36 rdf:rest Ne3235082230844069c320f203a28e2fe
37 N5148d07748d84fe7886d049f74587bac schema:name dimensions_id
38 schema:value pub.1048213566
39 rdf:type schema:PropertyValue
40 N63957b0392b449179ca198e6ab062166 schema:location Berlin, Heidelberg
41 schema:name Springer Berlin Heidelberg
42 rdf:type schema:Organisation
43 N823f8b4e80644d9984f37165408c1894 schema:familyName Bonuccelli
44 schema:givenName M.
45 rdf:type schema:Person
46 N97d374da67d442d38f6368a5de7aa6a0 schema:isbn 978-3-540-48337-3
47 978-3-540-57811-6
48 schema:name Algorithms and Complexity
49 rdf:type schema:Book
50 Nb88baed7dd11495aa1c0638da7a200fb schema:familyName Petreschi
51 schema:givenName R.
52 rdf:type schema:Person
53 Nc7e254ae8e4346ffad48e87be7b89a34 schema:familyName Crescenzi
54 schema:givenName P.
55 rdf:type schema:Person
56 Nd4f3ff2b4dc84e79a1ed8b3077c280d0 rdf:first Nb88baed7dd11495aa1c0638da7a200fb
57 rdf:rest rdf:nil
58 Ne3235082230844069c320f203a28e2fe rdf:first Nc7e254ae8e4346ffad48e87be7b89a34
59 rdf:rest Nd4f3ff2b4dc84e79a1ed8b3077c280d0
60 Ned52b03f769743289794776dcf3a5a2f schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
63 schema:name Information and Computing Sciences
64 rdf:type schema:DefinedTerm
65 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
66 schema:name Computation Theory and Mathematics
67 rdf:type schema:DefinedTerm
68 sg:person.015632520461.69 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
69 schema:familyName Alimonti
70 schema:givenName Paola
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69
72 rdf:type schema:Person
73 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
74 schema:name Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, via Salaria 113, 00198 Roma, Italia
75 rdf:type schema:Organization
 




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


...