On the number of iterations of Karmarkar's algorithm for linear programming View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-02

AUTHORS

M. J. D. Powell

ABSTRACT

Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a “potential function” by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method. More... »

PAGES

153-197

References to SciGraph publications

Journal

TITLE

Mathematical Programming

ISSUE

1-3

VOLUME

62

Author Affiliations

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "University of Cambridge", 
          "id": "https://www.grid.ac/institutes/grid.5335.0", 
          "name": [
            "Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, CB3 9EW, Cambridge, England"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Powell", 
        "givenName": "M. J. D.", 
        "id": "sg:person.07731545105.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01587095", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014973872", 
          "https://doi.org/10.1007/bf01587095"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02592025", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018061985", 
          "https://doi.org/10.1007/bf02592025"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02592025", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018061985", 
          "https://doi.org/10.1007/bf02592025"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01582888", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034599332", 
          "https://doi.org/10.1007/bf01582888"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579150", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035950209", 
          "https://doi.org/10.1007/bf02579150"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579150", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035950209", 
          "https://doi.org/10.1007/bf02579150"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840455", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038753043", 
          "https://doi.org/10.1007/bf01840455"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840455", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038753043", 
          "https://doi.org/10.1007/bf01840455"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(91)90040-v", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039685537"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(91)90040-v", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039685537"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0024-3795(91)90275-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041841057"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0801003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062854116"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0801018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062854131"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.14.1.97", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064723379"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1993-02", 
    "datePublishedReg": "1993-02-01", 
    "description": "Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a \u201cpotential function\u201d by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01585165", 
    "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": "62"
      }
    ], 
    "name": "On the number of iterations of Karmarkar's algorithm for linear programming", 
    "pagination": "153-197", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "56db4839ca9b4744e136582396eab5b0c9720c4bc445219c5ff33f9dba3de599"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01585165"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018229448"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01585165", 
      "https://app.dimensions.ai/details/publication/pub.1018229448"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T23: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/0000000001_0000000264/records_8693_00000531.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF01585165"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

96 TRIPLES      21 PREDICATES      37 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01585165 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N63f33725fa84455199d753570f22c885
4 schema:citation sg:pub.10.1007/bf01582888
5 sg:pub.10.1007/bf01587095
6 sg:pub.10.1007/bf01840455
7 sg:pub.10.1007/bf02579150
8 sg:pub.10.1007/bf02592025
9 https://doi.org/10.1016/0024-3795(91)90275-2
10 https://doi.org/10.1016/0167-6377(91)90040-v
11 https://doi.org/10.1137/0801003
12 https://doi.org/10.1137/0801018
13 https://doi.org/10.1287/moor.14.1.97
14 schema:datePublished 1993-02
15 schema:datePublishedReg 1993-02-01
16 schema:description Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a “potential function” by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.
17 schema:genre research_article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N9baca4821e4544f79958015c8c9ab80b
21 Nfcf36258689945db834009c66df83bf6
22 sg:journal.1047630
23 schema:name On the number of iterations of Karmarkar's algorithm for linear programming
24 schema:pagination 153-197
25 schema:productId N03154fceaa5043979563a59eedb4b88e
26 Nbc77a1b7655b4dc6a3bea910e789210e
27 Nfc41c598d5bc4a469ef80a62f81c8fbe
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018229448
29 https://doi.org/10.1007/bf01585165
30 schema:sdDatePublished 2019-04-10T23:28
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N328fa44a35c546af82d589c9bc117806
33 schema:url http://link.springer.com/10.1007%2FBF01585165
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N03154fceaa5043979563a59eedb4b88e schema:name dimensions_id
38 schema:value pub.1018229448
39 rdf:type schema:PropertyValue
40 N328fa44a35c546af82d589c9bc117806 schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N63f33725fa84455199d753570f22c885 rdf:first sg:person.07731545105.07
43 rdf:rest rdf:nil
44 N9baca4821e4544f79958015c8c9ab80b schema:volumeNumber 62
45 rdf:type schema:PublicationVolume
46 Nbc77a1b7655b4dc6a3bea910e789210e schema:name readcube_id
47 schema:value 56db4839ca9b4744e136582396eab5b0c9720c4bc445219c5ff33f9dba3de599
48 rdf:type schema:PropertyValue
49 Nfc41c598d5bc4a469ef80a62f81c8fbe schema:name doi
50 schema:value 10.1007/bf01585165
51 rdf:type schema:PropertyValue
52 Nfcf36258689945db834009c66df83bf6 schema:issueNumber 1-3
53 rdf:type schema:PublicationIssue
54 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
55 schema:name Mathematical Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
58 schema:name Pure Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1047630 schema:issn 0025-5610
61 1436-4646
62 schema:name Mathematical Programming
63 rdf:type schema:Periodical
64 sg:person.07731545105.07 schema:affiliation https://www.grid.ac/institutes/grid.5335.0
65 schema:familyName Powell
66 schema:givenName M. J. D.
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07
68 rdf:type schema:Person
69 sg:pub.10.1007/bf01582888 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034599332
70 https://doi.org/10.1007/bf01582888
71 rdf:type schema:CreativeWork
72 sg:pub.10.1007/bf01587095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014973872
73 https://doi.org/10.1007/bf01587095
74 rdf:type schema:CreativeWork
75 sg:pub.10.1007/bf01840455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038753043
76 https://doi.org/10.1007/bf01840455
77 rdf:type schema:CreativeWork
78 sg:pub.10.1007/bf02579150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035950209
79 https://doi.org/10.1007/bf02579150
80 rdf:type schema:CreativeWork
81 sg:pub.10.1007/bf02592025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018061985
82 https://doi.org/10.1007/bf02592025
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1016/0024-3795(91)90275-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041841057
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1016/0167-6377(91)90040-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1039685537
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1137/0801003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854116
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1137/0801018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854131
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1287/moor.14.1.97 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064723379
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.5335.0 schema:alternateName University of Cambridge
95 schema:name Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, CB3 9EW, Cambridge, England
96 rdf:type schema:Organization
 




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


...