A new polynomial-time algorithm for linear programming View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1984-12

AUTHORS

N. Karmarkar

ABSTRACT

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n3.5L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. More... »

PAGES

373-395

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "AT&T Bell Laboratories, 07974, Murray Hill, NJ, U.S.A.", 
          "id": "http://www.grid.ac/institutes/grid.469490.6", 
          "name": [
            "AT&T Bell Laboratories, 07974, Murray Hill, NJ, U.S.A."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karmarkar", 
        "givenName": "N.", 
        "id": "sg:person.012767743421.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012767743421.72"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02579273", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010850152", 
          "https://doi.org/10.1007/bf02579273"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1984-12", 
    "datePublishedReg": "1984-12-01", 
    "description": "We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n3.5L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n2.5). We prove that given a polytopeP and a strictly interior point a \u03b5P, there is a projective transformation of the space that mapsP, a toP\u2032, a\u2032 having the following property. The ratio of the radius of the smallest sphere with center a\u2032, containingP\u2032 to the radius of the largest sphere with center a\u2032 contained inP\u2032 isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02579150", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "4"
      }
    ], 
    "keywords": [
      "new polynomial time algorithm", 
      "polynomial time algorithm", 
      "linear programming", 
      "projective transformation", 
      "sequence of points", 
      "ellipsoid algorithm", 
      "number of variables", 
      "interior point", 
      "optimal solution", 
      "polynomial time", 
      "arithmetic operations", 
      "algorithm", 
      "small spheres", 
      "number of bits", 
      "worst case", 
      "large spheres", 
      "programming", 
      "converges", 
      "wheren", 
      "polytopeP", 
      "radius", 
      "bit number", 
      "optimization", 
      "sphere", 
      "space", 
      "point", 
      "solution", 
      "number", 
      "transformation", 
      "variables", 
      "properties", 
      "input", 
      "applications", 
      "operation", 
      "bits", 
      "cases", 
      "\u03b5p", 
      "time", 
      "center", 
      "sequence", 
      "ratio", 
      "factors"
    ], 
    "name": "A new polynomial-time algorithm for linear programming", 
    "pagination": "373-395", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035950209"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02579150"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02579150", 
      "https://app.dimensions.ai/details/publication/pub.1035950209"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-08-04T16:49", 
    "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_169.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02579150"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

103 TRIPLES      21 PREDICATES      68 URIs      59 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02579150 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N94bcb83205744d2abfa0dcd593d346fd
4 schema:citation sg:pub.10.1007/bf02579273
5 schema:datePublished 1984-12
6 schema:datePublishedReg 1984-12-01
7 schema:description We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n3.5L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time.
8 schema:genre article
9 schema:isAccessibleForFree false
10 schema:isPartOf Nacc6c041765d45828972be4c979dd742
11 Nce3a7d199eea4b11bbdff0c3013c791f
12 sg:journal.1136493
13 schema:keywords algorithm
14 applications
15 arithmetic operations
16 bit number
17 bits
18 cases
19 center
20 converges
21 ellipsoid algorithm
22 factors
23 input
24 interior point
25 large spheres
26 linear programming
27 new polynomial time algorithm
28 number
29 number of bits
30 number of variables
31 operation
32 optimal solution
33 optimization
34 point
35 polynomial time
36 polynomial time algorithm
37 polytopeP
38 programming
39 projective transformation
40 properties
41 radius
42 ratio
43 sequence
44 sequence of points
45 small spheres
46 solution
47 space
48 sphere
49 time
50 transformation
51 variables
52 wheren
53 worst case
54 εp
55 schema:name A new polynomial-time algorithm for linear programming
56 schema:pagination 373-395
57 schema:productId N48334557a95f485e9f6a8cff622dd7ce
58 Ndc2d5ebeab8b4a5e8335f5042e2ef08d
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035950209
60 https://doi.org/10.1007/bf02579150
61 schema:sdDatePublished 2022-08-04T16:49
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N6bc774b1eb1047dba5a5f2c675521d21
64 schema:url https://doi.org/10.1007/bf02579150
65 sgo:license sg:explorer/license/
66 sgo:sdDataset articles
67 rdf:type schema:ScholarlyArticle
68 N48334557a95f485e9f6a8cff622dd7ce schema:name dimensions_id
69 schema:value pub.1035950209
70 rdf:type schema:PropertyValue
71 N6bc774b1eb1047dba5a5f2c675521d21 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N94bcb83205744d2abfa0dcd593d346fd rdf:first sg:person.012767743421.72
74 rdf:rest rdf:nil
75 Nacc6c041765d45828972be4c979dd742 schema:volumeNumber 4
76 rdf:type schema:PublicationVolume
77 Nce3a7d199eea4b11bbdff0c3013c791f schema:issueNumber 4
78 rdf:type schema:PublicationIssue
79 Ndc2d5ebeab8b4a5e8335f5042e2ef08d schema:name doi
80 schema:value 10.1007/bf02579150
81 rdf:type schema:PropertyValue
82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
83 schema:name Mathematical Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
86 schema:name Applied Mathematics
87 rdf:type schema:DefinedTerm
88 sg:journal.1136493 schema:issn 0209-9683
89 1439-6912
90 schema:name Combinatorica
91 schema:publisher Springer Nature
92 rdf:type schema:Periodical
93 sg:person.012767743421.72 schema:affiliation grid-institutes:grid.469490.6
94 schema:familyName Karmarkar
95 schema:givenName N.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012767743421.72
97 rdf:type schema:Person
98 sg:pub.10.1007/bf02579273 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010850152
99 https://doi.org/10.1007/bf02579273
100 rdf:type schema:CreativeWork
101 grid-institutes:grid.469490.6 schema:alternateName AT&T Bell Laboratories, 07974, Murray Hill, NJ, U.S.A.
102 schema:name AT&T Bell Laboratories, 07974, Murray Hill, NJ, U.S.A.
103 rdf:type schema:Organization
 




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


...