{"entities":{"Q761967":{"pageid":763816,"ns":120,"title":"Item:Q761967","lastrevid":48782242,"modified":"2026-01-05T20:36:19Z","type":"item","id":"Q761967","labels":{"en":{"language":"en","value":"A new polynomial-time algorithm for linear programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3889275"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$6CB2FBB6-9E31-47DA-A553-D146EFB7859A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60c27034a32cae929b73bead1a8ae8720060dd4d","datavalue":{"value":{"text":"A new polynomial-time algorithm for linear programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q761967$ADFE6731-C5D8-4081-A116-9A776D525154","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9684134ffadfbd92f543c5a6a5d065667ca390a4","datavalue":{"value":"0557.90065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$D013E716-92DA-4F7F-B30C-D335010F6DF1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4775ea6702f549a0ab508dc667e0199bda7176ad","datavalue":{"value":"10.1007/BF02579150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$826F526D-9CAD-4EC3-85B7-B3EE2ACCBBFB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$9D6E1B2E-480B-457C-87BE-B2869D6DE458","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q761967$DBD3BC3A-0670-4319-868A-52F8A868781E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6787a69928a224a987c63d8e7f052f4890d8db6a","datavalue":{"value":"This paper discusses a new polynomial time algorithm for linear programming (LP). It is an interior point method whose worst case computational complexity is \\(0(n^{3.5}L)\\) arithmetic operations on 0(L) bit numbers, where n is the number of variables and L is the number of bits in the input. The complexity bound for this algorithm is better than that for the ellipsoid algorithm by a factor of \\(0(n^{2.5}).\\)    The author shows that every LP can be transformed into the form: min cx subject to \\(x\\in \\Omega \\cap \\Delta\\), where \\(\\Omega\\) is the subspace \\(\\{\\) \\(x: Ax=0\\}\\) and \\(\\Delta\\) is the simplex \\(\\{\\) \\(x: x\\geq 0\\) and \\(\\Sigma x_ j=1\\}\\), and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form.    Let \\(a_ 0=(1/n)e\\), where e is the vector of all 1's in \\(R^ n\\). Let \\(B(a_ 0,r)\\), \\(B(a_ 0,R)\\) be respectively the largest sphere with center \\(a_ 0\\) lying in \\(\\Delta\\), and the smallest sphere with center \\(a_ 0\\) containing \\(\\Delta\\). Then \\(R/r=(n-1)\\). Using this he shows that if \\(a_ 0\\) is feasible, \\(a_ 0-r\\hat c\\), where \\(\\hat c\\) is the normalized vector which in the orthogonal projection of c in \\(\\Omega\\), is chosen to the minimum objective value by a factor of (1-1/(n-1)). This is the main result on which the algorithm is based.    The algorithm is initiated with a feasible solution \\(x^ 0>0\\), and it generates a descent sequence of positive feasible points \\(x^ 0,x^ 1,..\\).. In the kth step, the point \\(x^ k\\) is brought into the center of the simplex by a projective transformation, a step of the form described above is taken, and the inverse projective transformation is applied, leading to the next point \\(x^{k+1}\\), reducing the objective function value by a factor of 0(n). The sequence of points generated, converges to a near optimal solution in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q761967$22663562-BF96-45E7-BEFA-FD5F5DEA7A31","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$25B66E5E-E494-457A-AFCC-9E13728DF806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$B15FDFF2-9BE7-4B07-B06B-97293C62F085","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c09558af3febc530e287726b12c629c145abe17f","datavalue":{"value":"3889275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$E1A04C66-4EC7-4A31-838C-1CB39C22A485","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q761967$10F81F75-A37F-4EB6-B77A-24525DFE1102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06b081ca97398e6e22b07f21a43ec8ba1e545222","datavalue":{"value":"interior point method","type":"string"},"datatype":"string"},"type":"statement","id":"Q761967$5AE20186-71E7-431E-A869-EBCFF0CF7C4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q761967$94EA7974-6FFD-4633-A238-2FD084380BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd277e8686d70b081d659084b731bb83012dde94","datavalue":{"value":"near optimal solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q761967$A06D82A1-D65B-4E1B-B0F8-0123365E4A3B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c0f2189b9095fbe6abad22259c6f186fac9c5b36","datavalue":{"value":{"entity-type":"item","numeric-id":687088,"id":"Q687088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$B0405424-011F-4FC9-AB12-FA802AD1C739","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$97F6CF75-F0D9-404E-80D0-EB4F6211B195","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0760228e23a11641bc3440037dd3ee0cc91e24fa","datavalue":{"value":"Q29543194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$F2C539FA-CDD7-4A85-89A4-A1D3980BAB5B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$145C48BF-7761-4C5E-B2FA-1406857666C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$5B2E332E-4869-406C-A0ED-6BBF96671AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5ee04025f8e388651be4d4db71d838030df73da","datavalue":{"value":{"entity-type":"item","numeric-id":5799167,"id":"Q5799167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761967$0817A230-42B8-4003-A45B-3942806E2645","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b8c42887111f0d87038f40a9b9225ed650fab096","datavalue":{"value":"https://doi.org/10.1007/bf02579150","type":"string"},"datatype":"url"},"type":"statement","id":"Q761967$80475B74-0086-48A4-BA97-5D8673A2CFD1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"644e5ef4d1d61c5bf137a87e940ebf664c610ba6","datavalue":{"value":"W2611147814","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761967$2F2A469D-3CE2-4F53-89FA-2317ED2A6887","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de23f811e8d84882a5bce171c67a41bfd0ae23a1","datavalue":{"value":{"entity-type":"item","numeric-id":3028715,"id":"Q3028715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a97eb5068ee399fe1f0d9663dfc9eeac9db7efef","datavalue":{"value":{"amount":"+0.9002137780189514","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761967$C4D304EA-FBFE-43B9-A400-2303F9390F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"629f91c4ad3340b8bfa0bcec8464fe49a4f985e4","datavalue":{"value":{"entity-type":"item","numeric-id":920841,"id":"Q920841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acabba6484568e59f5a55bd98a24fa5fa57d194d","datavalue":{"value":{"amount":"+0.8981729745864868","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761967$2C5EE4F2-75D8-42D5-80D7-0A5D3953A9E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b22574890c0fb5e5b75dc4a909d47f4bba18e44","datavalue":{"value":{"entity-type":"item","numeric-id":4897161,"id":"Q4897161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a7709048b2e8b7f6b1e494e468a472b1e90bf45","datavalue":{"value":{"amount":"+0.8863558769226074","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761967$5734C643-8B66-4B1A-BB43-DF89A1FB8FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5e6c3a2480e71a9bee20b0cc07676eb0e64ee8a","datavalue":{"value":{"entity-type":"item","numeric-id":1108927,"id":"Q1108927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06777ac7d6d153b5f34d77377d4eb441ea85404b","datavalue":{"value":{"amount":"+0.8863275051116943","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761967$5721E292-3674-4979-840B-3D157A9CE23A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"245d91de43b7f58c73d34d06f0f3d0fa922b97a6","datavalue":{"value":{"entity-type":"item","numeric-id":4733661,"id":"Q4733661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04bf38dda53fdca6b06accb2c1f03a4040c617f9","datavalue":{"value":{"amount":"+0.8813198208808899","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761967$4EE6B3F4-EAB8-4629-B9CA-BFBF1EAE293D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:761967","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:761967"}}}}}