A polynomial-time algorithm, based on Newton's method, for linear programming View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1988-01

AUTHORS

James Renegar

ABSTRACT

A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.

PAGES

59-93

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Operations Research and Industrial Engineering, Cornell University, 14853, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "School of Operations Research and Industrial Engineering, Cornell University, 14853, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Renegar", 
        "givenName": "James", 
        "id": "sg:person.01221736460.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221736460.09"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1988-01", 
    "datePublishedReg": "1988-01-01", 
    "description": "A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01580724", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "40"
      }
    ], 
    "keywords": [
      "polynomial time algorithm", 
      "linear programming", 
      "polynomial time", 
      "algorithm", 
      "ellipsoid algorithm", 
      "programming", 
      "Karmarkar's algorithm", 
      "method", 
      "interior methods", 
      "proof", 
      "Newton method", 
      "time"
    ], 
    "name": "A polynomial-time algorithm, based on Newton's method, for linear programming", 
    "pagination": "59-93", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028120387"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01580724"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01580724", 
      "https://app.dimensions.ai/details/publication/pub.1028120387"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-08-04T16:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_211.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01580724"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

69 TRIPLES      20 PREDICATES      37 URIs      29 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01580724 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N50d77c05cefa4e97b049aa88aa71b567
4 schema:datePublished 1988-01
5 schema:datePublishedReg 1988-01-01
6 schema:description A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.
7 schema:genre article
8 schema:isAccessibleForFree false
9 schema:isPartOf N21b0021dce2841b89d57b5190805df6a
10 Ncdbfe43790284acebe8af9adb6519658
11 sg:journal.1047630
12 schema:keywords Karmarkar's algorithm
13 Newton method
14 algorithm
15 ellipsoid algorithm
16 interior methods
17 linear programming
18 method
19 polynomial time
20 polynomial time algorithm
21 programming
22 proof
23 time
24 schema:name A polynomial-time algorithm, based on Newton's method, for linear programming
25 schema:pagination 59-93
26 schema:productId N3be6776949ca475e8284a95b3f31a648
27 Nc2d85685a02342c18b4acb07865c2ed0
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028120387
29 https://doi.org/10.1007/bf01580724
30 schema:sdDatePublished 2022-08-04T16:50
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N0217da4745b34f3d9edf1c05ac6c9e98
33 schema:url https://doi.org/10.1007/bf01580724
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N0217da4745b34f3d9edf1c05ac6c9e98 schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N21b0021dce2841b89d57b5190805df6a schema:volumeNumber 40
40 rdf:type schema:PublicationVolume
41 N3be6776949ca475e8284a95b3f31a648 schema:name doi
42 schema:value 10.1007/bf01580724
43 rdf:type schema:PropertyValue
44 N50d77c05cefa4e97b049aa88aa71b567 rdf:first sg:person.01221736460.09
45 rdf:rest rdf:nil
46 Nc2d85685a02342c18b4acb07865c2ed0 schema:name dimensions_id
47 schema:value pub.1028120387
48 rdf:type schema:PropertyValue
49 Ncdbfe43790284acebe8af9adb6519658 schema:issueNumber 1-3
50 rdf:type schema:PublicationIssue
51 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
52 schema:name Information and Computing Sciences
53 rdf:type schema:DefinedTerm
54 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
55 schema:name Computation Theory and Mathematics
56 rdf:type schema:DefinedTerm
57 sg:journal.1047630 schema:issn 0025-5610
58 1436-4646
59 schema:name Mathematical Programming
60 schema:publisher Springer Nature
61 rdf:type schema:Periodical
62 sg:person.01221736460.09 schema:affiliation grid-institutes:grid.5386.8
63 schema:familyName Renegar
64 schema:givenName James
65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221736460.09
66 rdf:type schema:Person
67 grid-institutes:grid.5386.8 schema:alternateName School of Operations Research and Industrial Engineering, Cornell University, 14853, Ithaca, NY, USA
68 schema:name School of Operations Research and Industrial Engineering, Cornell University, 14853, Ithaca, NY, USA
69 rdf:type schema:Organization
 




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


...