Roof duality, complementation and persistency in quadratic 0–1 optimization View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1984-02

AUTHORS

P. L. Hammer, P. Hansen, B. Simeone

ABSTRACT

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenxi=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited. More... »

PAGES

121-155

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Hill Center, Rutgers University, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hammer", 
        "givenName": "P. L.", 
        "id": "sg:person.015740461177.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 Catholique de Louvain", 
          "id": "https://www.grid.ac/institutes/grid.7942.8", 
          "name": [
            "Institut d'Economie Scientifique et de Gestion, Lille, France", 
            "Facult\u00e9 Universitaire Catholique de Mons, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hansen", 
        "givenName": "P.", 
        "id": "sg:person.016640446116.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640446116.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Research Council", 
          "id": "https://www.grid.ac/institutes/grid.5326.2", 
          "name": [
            "Istituto \u2018M. Picone\u2019 per le Applicazioni del Calcolo, CNR, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "B.", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01593772", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003951487", 
          "https://doi.org/10.1007/bf01593772"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70343-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006955107"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-0348-5321-7_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009987277", 
          "https://doi.org/10.1007/978-3-0348-5321-7_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580444", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015126123", 
          "https://doi.org/10.1007/bf01580444"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580444", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015126123", 
          "https://doi.org/10.1007/bf01580444"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-011-7557-9_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016373142", 
          "https://doi.org/10.1007/978-94-011-7557-9_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(79)90002-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023830880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0120892", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024466795", 
          "https://doi.org/10.1007/bfb0120892"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0120892", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024466795", 
          "https://doi.org/10.1007/bfb0120892"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70818-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033993779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70830-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043257851"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/b978-0-12-468662-5.50019-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049120999"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01588971", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049937899", 
          "https://doi.org/10.1007/bf01588971"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1050993949", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-85823-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050993949", 
          "https://doi.org/10.1007/978-3-642-85823-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-85823-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050993949", 
          "https://doi.org/10.1007/978-3-642-85823-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/800157.805047", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053230526"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0603052", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848777"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.17.3.200", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064716787"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1965-016-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072264633"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1984-02", 
    "datePublishedReg": "1984-02-01", 
    "description": "The paper is concerned with the \u2018primal\u2019 problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed\u2014the primal, the \u2018complementation\u2019, the \u2018discrete Rhys LP\u2019 and the \u2018weighted stability problem of a SAM graph\u2019. Each of them has a relaxation\u2014the \u2018roof dual\u2019, the \u2018quadratic complementation,\u2019 the \u2018continuous Rhys LP\u2019 and the \u2018fractional weighted stability problem of a SAM graph\u2019. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the \u2018roof-dual\u2019 define \u2018best\u2019 linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenxi=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02612354", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "28"
      }
    ], 
    "name": "Roof duality, complementation and persistency in quadratic 0\u20131 optimization", 
    "pagination": "121-155", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d72dee06d1e4e26b815b9845b43e02f76d8c716ec374e3f52d3c5b1be7b439f7"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02612354"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045174000"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02612354", 
      "https://app.dimensions.ai/details/publication/pub.1045174000"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:28", 
    "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/0000000370_0000000370/records_46741_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02612354"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

139 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02612354 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ncbe449ea9fcb4169a2a712a293cfe558
4 schema:citation sg:pub.10.1007/978-3-0348-5321-7_5
5 sg:pub.10.1007/978-3-642-85823-9
6 sg:pub.10.1007/978-94-011-7557-9_21
7 sg:pub.10.1007/bf01580444
8 sg:pub.10.1007/bf01588971
9 sg:pub.10.1007/bf01593772
10 sg:pub.10.1007/bfb0120892
11 https://app.dimensions.ai/details/publication/pub.1050993949
12 https://doi.org/10.1016/0020-0190(79)90002-4
13 https://doi.org/10.1016/b978-0-12-468662-5.50019-7
14 https://doi.org/10.1016/s0167-5060(08)70343-1
15 https://doi.org/10.1016/s0167-5060(08)70818-5
16 https://doi.org/10.1016/s0167-5060(08)70830-6
17 https://doi.org/10.1137/0603052
18 https://doi.org/10.1145/800157.805047
19 https://doi.org/10.1287/mnsc.17.3.200
20 https://doi.org/10.4153/cjm-1965-016-2
21 schema:datePublished 1984-02
22 schema:datePublishedReg 1984-02-01
23 schema:description The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenxi=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.
24 schema:genre research_article
25 schema:inLanguage en
26 schema:isAccessibleForFree false
27 schema:isPartOf Ncf4c07e8f215493691e23bf7e44e5951
28 Nd8dbf2de54ce48fc88806638f82ca48f
29 sg:journal.1047630
30 schema:name Roof duality, complementation and persistency in quadratic 0–1 optimization
31 schema:pagination 121-155
32 schema:productId N0a99c6c2afe545ef87d478a22aacbcb3
33 N3ef16e1c085643b58d1e4f86ebeb8a9d
34 Ndc22854696ec46fe8fbd52b0c90cc895
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045174000
36 https://doi.org/10.1007/bf02612354
37 schema:sdDatePublished 2019-04-11T13:28
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher Ne4a197e7c755409d8b0f7ec7b6f4c2f0
40 schema:url http://link.springer.com/10.1007%2FBF02612354
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N0751c048709645498b4943b1d3669718 rdf:first sg:person.012600006066.78
45 rdf:rest rdf:nil
46 N0a99c6c2afe545ef87d478a22aacbcb3 schema:name readcube_id
47 schema:value d72dee06d1e4e26b815b9845b43e02f76d8c716ec374e3f52d3c5b1be7b439f7
48 rdf:type schema:PropertyValue
49 N3ef16e1c085643b58d1e4f86ebeb8a9d schema:name doi
50 schema:value 10.1007/bf02612354
51 rdf:type schema:PropertyValue
52 Nb4cdb063f53643f48be03a6476fdd1f2 rdf:first sg:person.016640446116.30
53 rdf:rest N0751c048709645498b4943b1d3669718
54 Ncbe449ea9fcb4169a2a712a293cfe558 rdf:first sg:person.015740461177.00
55 rdf:rest Nb4cdb063f53643f48be03a6476fdd1f2
56 Ncf4c07e8f215493691e23bf7e44e5951 schema:issueNumber 2
57 rdf:type schema:PublicationIssue
58 Nd8dbf2de54ce48fc88806638f82ca48f schema:volumeNumber 28
59 rdf:type schema:PublicationVolume
60 Ndc22854696ec46fe8fbd52b0c90cc895 schema:name dimensions_id
61 schema:value pub.1045174000
62 rdf:type schema:PropertyValue
63 Ne4a197e7c755409d8b0f7ec7b6f4c2f0 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
66 schema:name Mathematical Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
69 schema:name Pure Mathematics
70 rdf:type schema:DefinedTerm
71 sg:journal.1047630 schema:issn 0025-5610
72 1436-4646
73 schema:name Mathematical Programming
74 rdf:type schema:Periodical
75 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.5326.2
76 schema:familyName Simeone
77 schema:givenName B.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
79 rdf:type schema:Person
80 sg:person.015740461177.00 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
81 schema:familyName Hammer
82 schema:givenName P. L.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00
84 rdf:type schema:Person
85 sg:person.016640446116.30 schema:affiliation https://www.grid.ac/institutes/grid.7942.8
86 schema:familyName Hansen
87 schema:givenName P.
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640446116.30
89 rdf:type schema:Person
90 sg:pub.10.1007/978-3-0348-5321-7_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009987277
91 https://doi.org/10.1007/978-3-0348-5321-7_5
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/978-3-642-85823-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050993949
94 https://doi.org/10.1007/978-3-642-85823-9
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/978-94-011-7557-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016373142
97 https://doi.org/10.1007/978-94-011-7557-9_21
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bf01580444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015126123
100 https://doi.org/10.1007/bf01580444
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/bf01588971 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049937899
103 https://doi.org/10.1007/bf01588971
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bf01593772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003951487
106 https://doi.org/10.1007/bf01593772
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bfb0120892 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024466795
109 https://doi.org/10.1007/bfb0120892
110 rdf:type schema:CreativeWork
111 https://app.dimensions.ai/details/publication/pub.1050993949 schema:CreativeWork
112 https://doi.org/10.1016/0020-0190(79)90002-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023830880
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/b978-0-12-468662-5.50019-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049120999
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0167-5060(08)70343-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006955107
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/s0167-5060(08)70818-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033993779
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1016/s0167-5060(08)70830-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043257851
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/0603052 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848777
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/800157.805047 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053230526
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1287/mnsc.17.3.200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064716787
127 rdf:type schema:CreativeWork
128 https://doi.org/10.4153/cjm-1965-016-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264633
129 rdf:type schema:CreativeWork
130 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
131 schema:name RUTCOR, Hill Center, Rutgers University, New Brunswick, NJ, USA
132 rdf:type schema:Organization
133 https://www.grid.ac/institutes/grid.5326.2 schema:alternateName National Research Council
134 schema:name Istituto ‘M. Picone’ per le Applicazioni del Calcolo, CNR, Rome, Italy
135 rdf:type schema:Organization
136 https://www.grid.ac/institutes/grid.7942.8 schema:alternateName Université Catholique de Louvain
137 schema:name Faculté Universitaire Catholique de Mons, Belgium
138 Institut d'Economie Scientifique et de Gestion, Lille, France
139 rdf:type schema:Organization
 




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


...