Small Chvátal Rank View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2010-07

AUTHORS

Tristram Bogart, Annie Raymond, Rekha Thomas

ABSTRACT

We propose a variant of the Chvátal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x : Ax ≤ b} as b varies. The number of steps needed is called the small Chvátal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube. More... »

PAGES

45-68

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10107-010-0370-x

DOI

http://dx.doi.org/10.1007/s10107-010-0370-x

DIMENSIONS

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


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/1117", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Public Health and Health Services", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Queen's University", 
          "id": "https://www.grid.ac/institutes/grid.410356.5", 
          "name": [
            "Department of Mathematics and Statistics, Queen\u2019s University, K7L 3N6, Kingston, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bogart", 
        "givenName": "Tristram", 
        "id": "sg:person.011504445413.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011504445413.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical University of Berlin", 
          "id": "https://www.grid.ac/institutes/grid.6734.6", 
          "name": [
            "Berlin Mathematical School, Technical University, 10623, Berlin, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raymond", 
        "givenName": "Annie", 
        "id": "sg:person.010224546073.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010224546073.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Washington", 
          "id": "https://www.grid.ac/institutes/grid.34477.33", 
          "name": [
            "Department of Mathematics, University of Washington, 98195-4350, Seattle, WA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Thomas", 
        "givenName": "Rekha", 
        "id": "sg:person.016476102733.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016476102733.25"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s001860300317", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004970526", 
          "https://doi.org/10.1007/s001860300317"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00493-003-0020-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006302584", 
          "https://doi.org/10.1007/s00493-003-0020-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0097-3165(03)00117-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008127552"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0097-3165(03)00117-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008127552"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00011376", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017960070", 
          "https://doi.org/10.1007/pl00011376"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcta.1997.2780", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018065990"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/b:jaco.0000030705.93448.ce", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020914780", 
          "https://doi.org/10.1023/b:jaco.0000030705.93448.ce"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/b:jaco.0000030705.93448.ce", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020914780", 
          "https://doi.org/10.1023/b:jaco.0000030705.93448.ce"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0894-0347-03-00428-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021745420"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01581273", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028395699", 
          "https://doi.org/10.1007/bf01581273"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01581273", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028395699", 
          "https://doi.org/10.1007/bf01581273"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jctb.1996.1715", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031673149"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1033583445", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-78240-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033583445", 
          "https://doi.org/10.1007/978-3-642-78240-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-78240-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033583445", 
          "https://doi.org/10.1007/978-3-642-78240-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(73)90167-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034063944"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(80)90075-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038079648"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(81)90033-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043746311"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0403036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844627"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0801013", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062854126"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.24.1.1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064724174"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-07", 
    "datePublishedReg": "2010-07-01", 
    "description": "We propose a variant of the Chv\u00e1tal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x : Ax \u2264 b} as b varies. The number of steps needed is called the small Chv\u00e1tal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10107-010-0370-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "124"
      }
    ], 
    "name": "Small Chv\u00e1tal Rank", 
    "pagination": "45-68", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f6a073fc05b418c9be974915d95abe771679a0c974616fc0218abe3cc2d946ea"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10107-010-0370-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051775020"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10107-010-0370-x", 
      "https://app.dimensions.ai/details/publication/pub.1051775020"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10: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/0000000349_0000000349/records_113640_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs10107-010-0370-x"
  }
]
 

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/s10107-010-0370-x'

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/s10107-010-0370-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10107-010-0370-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10107-010-0370-x'


 

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

137 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10107-010-0370-x schema:about anzsrc-for:11
2 anzsrc-for:1117
3 schema:author N3fee856d963f4aa4ae76e56d06466797
4 schema:citation sg:pub.10.1007/978-3-642-78240-4
5 sg:pub.10.1007/bf01581273
6 sg:pub.10.1007/pl00011376
7 sg:pub.10.1007/s001860300317
8 sg:pub.10.1007/s00493-003-0020-5
9 sg:pub.10.1023/b:jaco.0000030705.93448.ce
10 https://app.dimensions.ai/details/publication/pub.1033583445
11 https://doi.org/10.1006/jcta.1997.2780
12 https://doi.org/10.1006/jctb.1996.1715
13 https://doi.org/10.1016/0012-365x(73)90167-2
14 https://doi.org/10.1016/0095-8956(80)90075-1
15 https://doi.org/10.1016/0095-8956(81)90033-2
16 https://doi.org/10.1016/s0097-3165(03)00117-1
17 https://doi.org/10.1090/s0894-0347-03-00428-4
18 https://doi.org/10.1137/0403036
19 https://doi.org/10.1137/0801013
20 https://doi.org/10.1287/moor.24.1.1
21 schema:datePublished 2010-07
22 schema:datePublishedReg 2010-07-01
23 schema:description We propose a variant of the Chvátal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x : Ax ≤ b} as b varies. The number of steps needed is called the small Chvátal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.
24 schema:genre research_article
25 schema:inLanguage en
26 schema:isAccessibleForFree false
27 schema:isPartOf Nd7e694c8604d4f749c365bcb14464f0a
28 Ndcd419f8d8d845cab719e4e7a69b3499
29 sg:journal.1047630
30 schema:name Small Chvátal Rank
31 schema:pagination 45-68
32 schema:productId N03dbc57e19d743e88c231dbddd9b82fe
33 N64138aeff50945549fd9494b1f8f0231
34 N7b97996076e2431f826c1e41b7bfcef0
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051775020
36 https://doi.org/10.1007/s10107-010-0370-x
37 schema:sdDatePublished 2019-04-11T10:28
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N161f3fd0b7e54a638d8a7bb007cf80f1
40 schema:url http://link.springer.com/10.1007%2Fs10107-010-0370-x
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N03dbc57e19d743e88c231dbddd9b82fe schema:name dimensions_id
45 schema:value pub.1051775020
46 rdf:type schema:PropertyValue
47 N161f3fd0b7e54a638d8a7bb007cf80f1 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N3fee856d963f4aa4ae76e56d06466797 rdf:first sg:person.011504445413.92
50 rdf:rest N60c3525d8ae4480ea560e7fa18d03869
51 N60c3525d8ae4480ea560e7fa18d03869 rdf:first sg:person.010224546073.87
52 rdf:rest N9188d8f0cc774e8b9c7dfa8f0fd60dae
53 N64138aeff50945549fd9494b1f8f0231 schema:name readcube_id
54 schema:value f6a073fc05b418c9be974915d95abe771679a0c974616fc0218abe3cc2d946ea
55 rdf:type schema:PropertyValue
56 N7b97996076e2431f826c1e41b7bfcef0 schema:name doi
57 schema:value 10.1007/s10107-010-0370-x
58 rdf:type schema:PropertyValue
59 N9188d8f0cc774e8b9c7dfa8f0fd60dae rdf:first sg:person.016476102733.25
60 rdf:rest rdf:nil
61 Nd7e694c8604d4f749c365bcb14464f0a schema:volumeNumber 124
62 rdf:type schema:PublicationVolume
63 Ndcd419f8d8d845cab719e4e7a69b3499 schema:issueNumber 1-2
64 rdf:type schema:PublicationIssue
65 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
66 schema:name Medical and Health Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
69 schema:name Public Health and Health Services
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.010224546073.87 schema:affiliation https://www.grid.ac/institutes/grid.6734.6
76 schema:familyName Raymond
77 schema:givenName Annie
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010224546073.87
79 rdf:type schema:Person
80 sg:person.011504445413.92 schema:affiliation https://www.grid.ac/institutes/grid.410356.5
81 schema:familyName Bogart
82 schema:givenName Tristram
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011504445413.92
84 rdf:type schema:Person
85 sg:person.016476102733.25 schema:affiliation https://www.grid.ac/institutes/grid.34477.33
86 schema:familyName Thomas
87 schema:givenName Rekha
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016476102733.25
89 rdf:type schema:Person
90 sg:pub.10.1007/978-3-642-78240-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033583445
91 https://doi.org/10.1007/978-3-642-78240-4
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/bf01581273 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028395699
94 https://doi.org/10.1007/bf01581273
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/pl00011376 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017960070
97 https://doi.org/10.1007/pl00011376
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/s001860300317 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004970526
100 https://doi.org/10.1007/s001860300317
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s00493-003-0020-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006302584
103 https://doi.org/10.1007/s00493-003-0020-5
104 rdf:type schema:CreativeWork
105 sg:pub.10.1023/b:jaco.0000030705.93448.ce schema:sameAs https://app.dimensions.ai/details/publication/pub.1020914780
106 https://doi.org/10.1023/b:jaco.0000030705.93448.ce
107 rdf:type schema:CreativeWork
108 https://app.dimensions.ai/details/publication/pub.1033583445 schema:CreativeWork
109 https://doi.org/10.1006/jcta.1997.2780 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018065990
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1006/jctb.1996.1715 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031673149
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/0012-365x(73)90167-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034063944
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/0095-8956(80)90075-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038079648
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/0095-8956(81)90033-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043746311
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/s0097-3165(03)00117-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008127552
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1090/s0894-0347-03-00428-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021745420
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1137/0403036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844627
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1137/0801013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854126
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1287/moor.24.1.1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724174
128 rdf:type schema:CreativeWork
129 https://www.grid.ac/institutes/grid.34477.33 schema:alternateName University of Washington
130 schema:name Department of Mathematics, University of Washington, 98195-4350, Seattle, WA, USA
131 rdf:type schema:Organization
132 https://www.grid.ac/institutes/grid.410356.5 schema:alternateName Queen's University
133 schema:name Department of Mathematics and Statistics, Queen’s University, K7L 3N6, Kingston, ON, Canada
134 rdf:type schema:Organization
135 https://www.grid.ac/institutes/grid.6734.6 schema:alternateName Technical University of Berlin
136 schema:name Berlin Mathematical School, Technical University, 10623, Berlin, Germany
137 rdf:type schema:Organization
 




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


...