On Simplex Pivoting Rules and Complexity Theory View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Ilan Adler , Christos Papadimitriou , Aviad Rubinstein

ABSTRACT

We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm’s path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig’s shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules. More... »

PAGES

13-24

Book

TITLE

Integer Programming and Combinatorial Optimization

ISBN

978-3-319-07556-3
978-3-319-07557-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-07557-0_2

DOI

http://dx.doi.org/10.1007/978-3-319-07557-0_2

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of California, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Adler", 
        "givenName": "Ilan", 
        "id": "sg:person.014157407520.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157407520.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rubinstein", 
        "givenName": "Aviad", 
        "id": "sg:person.012737202005.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012737202005.43"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm\u2019s path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig\u2019s shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules.", 
    "editor": [
      {
        "familyName": "Lee", 
        "givenName": "Jon", 
        "type": "Person"
      }, 
      {
        "familyName": "Vygen", 
        "givenName": "Jens", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-07557-0_2", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-07556-3", 
        "978-3-319-07557-0"
      ], 
      "name": "Integer Programming and Combinatorial Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "such rules", 
      "polynomial algorithm", 
      "algorithm", 
      "path problem", 
      "complexity theory", 
      "rules", 
      "particular basis", 
      "basis", 
      "algorithm paths", 
      "path", 
      "variants", 
      "simplex method", 
      "vertex algorithm", 
      "same context", 
      "method", 
      "context", 
      "theory", 
      "problem", 
      "Dantzig\u2019s shadow vertex algorithm", 
      "\u2019s shadow vertex algorithm", 
      "polynomial path problem", 
      "Simplex Pivoting Rules", 
      "Pivoting Rules"
    ], 
    "name": "On Simplex Pivoting Rules and Complexity Theory", 
    "pagination": "13-24", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009877850"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-07557-0_2"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-07557-0_2", 
      "https://app.dimensions.ai/details/publication/pub.1009877850"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_106.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-07557-0_2"
  }
]
 

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-319-07557-0_2'

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-319-07557-0_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-07557-0_2'

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-319-07557-0_2'


 

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

102 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-07557-0_2 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nc50fd0b8987840e6bec5f5ac306e4447
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm’s path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig’s shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules.
7 schema:editor N68900d2ac057412d91e03402f217a582
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N0da277e4847343569e560377e80b48c0
12 schema:keywords Dantzig’s shadow vertex algorithm
13 Pivoting Rules
14 Simplex Pivoting Rules
15 algorithm
16 algorithm paths
17 basis
18 complexity theory
19 context
20 method
21 particular basis
22 path
23 path problem
24 polynomial algorithm
25 polynomial path problem
26 problem
27 rules
28 same context
29 simplex method
30 such rules
31 theory
32 variants
33 vertex algorithm
34 ’s shadow vertex algorithm
35 schema:name On Simplex Pivoting Rules and Complexity Theory
36 schema:pagination 13-24
37 schema:productId N2666cac757ac442e9da1a598e15584e6
38 N63e2aafe413a467ebd65a57697650647
39 schema:publisher N507552d5d70f4383b1171673de2bd33d
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009877850
41 https://doi.org/10.1007/978-3-319-07557-0_2
42 schema:sdDatePublished 2021-11-01T18:45
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Ne6cf8d99d05c4306833a7ff9e6240e60
45 schema:url https://doi.org/10.1007/978-3-319-07557-0_2
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N0da277e4847343569e560377e80b48c0 schema:isbn 978-3-319-07556-3
50 978-3-319-07557-0
51 schema:name Integer Programming and Combinatorial Optimization
52 rdf:type schema:Book
53 N2666cac757ac442e9da1a598e15584e6 schema:name dimensions_id
54 schema:value pub.1009877850
55 rdf:type schema:PropertyValue
56 N3846254815b442409e9eab3ee3974a86 schema:familyName Lee
57 schema:givenName Jon
58 rdf:type schema:Person
59 N507552d5d70f4383b1171673de2bd33d schema:name Springer Nature
60 rdf:type schema:Organisation
61 N63e2aafe413a467ebd65a57697650647 schema:name doi
62 schema:value 10.1007/978-3-319-07557-0_2
63 rdf:type schema:PropertyValue
64 N68900d2ac057412d91e03402f217a582 rdf:first N3846254815b442409e9eab3ee3974a86
65 rdf:rest N71283172fd114923af54ecc5ca95a525
66 N71283172fd114923af54ecc5ca95a525 rdf:first N74e111d59d654f328da08c909ef7f6ba
67 rdf:rest rdf:nil
68 N74e111d59d654f328da08c909ef7f6ba schema:familyName Vygen
69 schema:givenName Jens
70 rdf:type schema:Person
71 N79d06ea9082343718e83f4b29af7fcb4 rdf:first sg:person.012737202005.43
72 rdf:rest rdf:nil
73 Nc50fd0b8987840e6bec5f5ac306e4447 rdf:first sg:person.014157407520.34
74 rdf:rest Ncdc4e3ed164840c4bf4be5263a95f692
75 Ncdc4e3ed164840c4bf4be5263a95f692 rdf:first sg:person.013233165465.63
76 rdf:rest N79d06ea9082343718e83f4b29af7fcb4
77 Ne6cf8d99d05c4306833a7ff9e6240e60 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
80 schema:name Mathematical Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
83 schema:name Pure Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.012737202005.43 schema:affiliation grid-institutes:grid.47840.3f
86 schema:familyName Rubinstein
87 schema:givenName Aviad
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012737202005.43
89 rdf:type schema:Person
90 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
91 schema:familyName Papadimitriou
92 schema:givenName Christos
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
94 rdf:type schema:Person
95 sg:person.014157407520.34 schema:affiliation grid-institutes:grid.47840.3f
96 schema:familyName Adler
97 schema:givenName Ilan
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157407520.34
99 rdf:type schema:Person
100 grid-institutes:grid.47840.3f schema:alternateName University of California, 94720, Berkeley, CA, USA
101 schema:name University of California, 94720, Berkeley, CA, USA
102 rdf:type schema:Organization
 




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


...