On the supermodular knapsack problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-08

AUTHORS

G. Gallo, B. Simeone

ABSTRACT

In this paper we introduce binary knapsack problems where the objective function is nonlinear, and investigate their Lagrangean and continuous relaxations. Some of our results generalize previously known theorems concerning linear and quadratic knapsack problems. We investigate in particular the case in which the objective function is supermodular. Under this hypothesis, although the problem remains NP-hard, we show that its Lagrangean dual and its continuous relaxation can be solved in polynomial time. We also comment on the complexity of recognizing supermodular functions. The particular case in which the knapsack constraint is of the cardinality type is also addressed and some properties of its optimal value as a function of the right hand side are derived. More... »

PAGES

295-309

References to SciGraph publications

  • 1981-06. The ellipsoid method and its consequences in combinatorial optimization in COMBINATORICA
  • 1972. Reducibility among Combinatorial Problems in COMPLEXITY OF COMPUTER COMPUTATIONS
  • 2009-02-24. Quadratic knapsack problems in COMBINATORIAL OPTIMIZATION
  • 1978-12. An analysis of approximations for maximizing submodular set functions—I in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "University of Pisa", 
              "id": "https://www.grid.ac/institutes/grid.5395.a", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 di Pisa, 56100, Pisa, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gallo", 
            "givenName": "G.", 
            "id": "sg:person.07360703527.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07360703527.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento de Statistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, 00185, 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": "https://doi.org/10.1016/s0167-5060(08)70043-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002898575"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007977430", 
              "https://doi.org/10.1007/978-1-4684-2001-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579273", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010850152", 
              "https://doi.org/10.1007/bf02579273"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579273", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010850152", 
              "https://doi.org/10.1007/bf02579273"
            ], 
            "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/0166-218x(85)90035-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037865607"
            ], 
            "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://doi.org/10.1287/opre.26.2.305", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064728893"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1989-08", 
        "datePublishedReg": "1989-08-01", 
        "description": "In this paper we introduce binary knapsack problems where the objective function is nonlinear, and investigate their Lagrangean and continuous relaxations. Some of our results generalize previously known theorems concerning linear and quadratic knapsack problems. We investigate in particular the case in which the objective function is supermodular. Under this hypothesis, although the problem remains NP-hard, we show that its Lagrangean dual and its continuous relaxation can be solved in polynomial time. We also comment on the complexity of recognizing supermodular functions. The particular case in which the knapsack constraint is of the cardinality type is also addressed and some properties of its optimal value as a function of the right hand side are derived.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01589108", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047630", 
            "issn": [
              "0025-5610", 
              "1436-4646"
            ], 
            "name": "Mathematical Programming", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "45"
          }
        ], 
        "name": "On the supermodular knapsack problem", 
        "pagination": "295-309", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "fb483632a75c05dbe6b8c3c4963e2f5e5948975ed4391d41bd47651aa019610c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01589108"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1052753711"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01589108", 
          "https://app.dimensions.ai/details/publication/pub.1052753711"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T23:29", 
        "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_8693_00000535.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF01589108"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    96 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01589108 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N1b3ad7a2dab94327b212d8908b2d3361
    4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
    5 sg:pub.10.1007/bf01588971
    6 sg:pub.10.1007/bf02579273
    7 sg:pub.10.1007/bfb0120892
    8 https://doi.org/10.1016/0166-218x(85)90035-6
    9 https://doi.org/10.1016/s0167-5060(08)70043-8
    10 https://doi.org/10.1287/opre.26.2.305
    11 schema:datePublished 1989-08
    12 schema:datePublishedReg 1989-08-01
    13 schema:description In this paper we introduce binary knapsack problems where the objective function is nonlinear, and investigate their Lagrangean and continuous relaxations. Some of our results generalize previously known theorems concerning linear and quadratic knapsack problems. We investigate in particular the case in which the objective function is supermodular. Under this hypothesis, although the problem remains NP-hard, we show that its Lagrangean dual and its continuous relaxation can be solved in polynomial time. We also comment on the complexity of recognizing supermodular functions. The particular case in which the knapsack constraint is of the cardinality type is also addressed and some properties of its optimal value as a function of the right hand side are derived.
    14 schema:genre research_article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N3712a72ca8d54ee5a835f9d82519cbfc
    18 Nefc485f115b748428b323e663f5b36e5
    19 sg:journal.1047630
    20 schema:name On the supermodular knapsack problem
    21 schema:pagination 295-309
    22 schema:productId N2a46eeef5893472683695f49fdfe95d2
    23 N2f7fd8112d0a420180795120f2c35bfc
    24 Nf77c98135258496383a5a627a9b83012
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052753711
    26 https://doi.org/10.1007/bf01589108
    27 schema:sdDatePublished 2019-04-10T23:29
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher Nbd6cdc7f5c394ec7b59c875775e93f28
    30 schema:url http://link.springer.com/10.1007%2FBF01589108
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N1b3ad7a2dab94327b212d8908b2d3361 rdf:first sg:person.07360703527.19
    35 rdf:rest N74d0dea74fa54d819b36159514f0a84d
    36 N2a46eeef5893472683695f49fdfe95d2 schema:name doi
    37 schema:value 10.1007/bf01589108
    38 rdf:type schema:PropertyValue
    39 N2f7fd8112d0a420180795120f2c35bfc schema:name dimensions_id
    40 schema:value pub.1052753711
    41 rdf:type schema:PropertyValue
    42 N3712a72ca8d54ee5a835f9d82519cbfc schema:volumeNumber 45
    43 rdf:type schema:PublicationVolume
    44 N74d0dea74fa54d819b36159514f0a84d rdf:first sg:person.012600006066.78
    45 rdf:rest rdf:nil
    46 Nbd6cdc7f5c394ec7b59c875775e93f28 schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 Nefc485f115b748428b323e663f5b36e5 schema:issueNumber 1-3
    49 rdf:type schema:PublicationIssue
    50 Nf77c98135258496383a5a627a9b83012 schema:name readcube_id
    51 schema:value fb483632a75c05dbe6b8c3c4963e2f5e5948975ed4391d41bd47651aa019610c
    52 rdf:type schema:PropertyValue
    53 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    54 schema:name Information and Computing Sciences
    55 rdf:type schema:DefinedTerm
    56 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Computation Theory and Mathematics
    58 rdf:type schema:DefinedTerm
    59 sg:journal.1047630 schema:issn 0025-5610
    60 1436-4646
    61 schema:name Mathematical Programming
    62 rdf:type schema:Periodical
    63 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    64 schema:familyName Simeone
    65 schema:givenName B.
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
    67 rdf:type schema:Person
    68 sg:person.07360703527.19 schema:affiliation https://www.grid.ac/institutes/grid.5395.a
    69 schema:familyName Gallo
    70 schema:givenName G.
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07360703527.19
    72 rdf:type schema:Person
    73 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
    74 https://doi.org/10.1007/978-1-4684-2001-2_9
    75 rdf:type schema:CreativeWork
    76 sg:pub.10.1007/bf01588971 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049937899
    77 https://doi.org/10.1007/bf01588971
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/bf02579273 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010850152
    80 https://doi.org/10.1007/bf02579273
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/bfb0120892 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024466795
    83 https://doi.org/10.1007/bfb0120892
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1016/0166-218x(85)90035-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037865607
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1016/s0167-5060(08)70043-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002898575
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1287/opre.26.2.305 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728893
    90 rdf:type schema:CreativeWork
    91 https://www.grid.ac/institutes/grid.5395.a schema:alternateName University of Pisa
    92 schema:name Dipartimento di Informatica, Università di Pisa, 56100, Pisa, Italy
    93 rdf:type schema:Organization
    94 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    95 schema:name Dipartimento de Statistica, Università di Roma “La Sapienza”, 00185, Rome, Italy
    96 rdf:type schema:Organization
     




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


    ...