{"entities":{"Q1824548":{"pageid":1835290,"ns":120,"title":"Item:Q1824548","lastrevid":69245655,"modified":"2026-04-13T05:43:47Z","type":"item","id":"Q1824548","labels":{"en":{"language":"en","value":"A simple complexity proof for a polynomial-time linear programming algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4118154"}},"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":"Q1824548$EC5A7274-DD7B-42B0-9967-9381B73FFA81","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c13af647cd9d7a42c204ead64d6a5bf87e4b6f56","datavalue":{"value":{"text":"A simple complexity proof for a polynomial-time linear programming algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1824548$7F61133A-46BE-44CE-B2B7-6BDA29DC0F49","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ee1d06ef74629de44acd04c863181c9b4f24adc6","datavalue":{"value":"0682.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$4C57EF87-5FF2-45A9-9FF4-80E1C2CBAC30","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d6772185091f2907c5929eedd653d0309526be7b","datavalue":{"value":"10.1016/0167-6377(89)90042-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$F7AC865D-0E44-436C-B3C1-424F35A8A4C6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$AE416761-3FE5-49C4-B04C-C2CC25EC45FB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1824548$B6D01BF8-B006-40D1-85B2-3F6DF2FE50D5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f065970380dec5ebb16c701c4cf92ee70a179e6","datavalue":{"value":"A variant of Karmarkar's polynomial-time algorithm for linear programming is given. A logarithmic penalty function is attached to the objective function and the resulting nonlinear problem is solved by using a sequence of quadratic approximations. There is a simple proof of complexity of \\(O(m^{1/2}L)\\) iterations and \\(O(m^{3,5}L)\\) arithmetic operations, where m is the number of variables and L is the size of the problem encoded in binary.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824548$42B9A948-16FC-4CFB-9465-90E687112206","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$92F8BC92-6637-47CC-930F-BA73402B5903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$148B5FF6-8E7C-4020-8417-F4E4582F72CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83b31f1cfd12ee97e3ddd389eadf959fa3d48d17","datavalue":{"value":"49M30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$E01AB2FD-7653-43E8-88C4-2DF5BBF0C632","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"929334de72a8172b49e92b154b2f6b027953d255","datavalue":{"value":"4118154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$F9155B64-F214-4D1D-A711-257B8CD784C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2c18bde8901327a1cf574f707d6e403feda0b41","datavalue":{"value":"Karmarkar's polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824548$B8DAFABF-230A-47B5-BE5D-EC6710CE9EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e71ca98ad51d56674925f66341d789f4d11ca49f","datavalue":{"value":"logarithmic penalty function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824548$CC4AB710-A70E-4B63-B585-E4F996E6F210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"793e3294b69b849c747a266f3a82b380ed4da06d","datavalue":{"value":"quadratic approximations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824548$D2A7B069-3741-41F7-838C-B6A14EE5643B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"51a0a867082299fcd65acab9bbebddcda8d10617","datavalue":{"value":{"entity-type":"item","numeric-id":535017,"id":"Q535017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$312518CF-BE18-4D6A-9F51-401D34A2ED76","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6f851cfac7ea7c4643b1d7cdb7841dc9bb3a301d","datavalue":{"value":{"entity-type":"item","numeric-id":216353,"id":"Q216353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$9D27DAE8-A4DE-4B66-99CD-01A35F59DF4E","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":"Q1824548$3DA1FE67-BF48-443F-9977-ECE98BC0B03E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ddbc8d9b0e043c20b60768628103081c76917fa9","datavalue":{"value":"https://doi.org/10.1016/0167-6377(89)90042-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1824548$48653C83-C632-4511-9D26-B347B079FB2C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"416b8871dbd100fd2a58c677c64e7155fe308b03","datavalue":{"value":"W2041934365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824548$4A33C3FA-152E-4DC3-8140-94EE3383CA31","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$E1EF1881-B32A-4AB2-9D11-30F3126CF4D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbefb3a4195c174b0697cf32d559babae40f18f","datavalue":{"value":{"entity-type":"item","numeric-id":3657778,"id":"Q3657778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$FCC66718-AACD-4770-B7AC-6A62E39B5B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2aa4eeac790205c4037ea67c80426826ddde338","datavalue":{"value":{"entity-type":"item","numeric-id":5638112,"id":"Q5638112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$DD774B1E-0EAB-4376-AE11-B37B84206D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e87b2bcedefc228296626d38707048b3185a0d41","datavalue":{"value":{"entity-type":"item","numeric-id":1149235,"id":"Q1149235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$32DF32C0-1869-427A-A37F-0FDEF2A7BC1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"418566d3cc45bced172ae8e6db85426ab845ceb3","datavalue":{"value":{"entity-type":"item","numeric-id":2483038,"id":"Q2483038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$6F534A4A-FC5A-4E48-9E88-41287122073A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1746c0002a982167f6b872896509d0ce78aa9e","datavalue":{"value":{"entity-type":"item","numeric-id":2536323,"id":"Q2536323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$3DF1CAFE-8FFE-489B-8C16-EFC2680D9D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53d400ae67354c276eb452acdccfbc71361c8b32","datavalue":{"value":{"entity-type":"item","numeric-id":1108927,"id":"Q1108927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$CBBEB751-A8DC-4854-8C4B-6C026215F4AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0645fdaa8941523699beeacef604bd643337295","datavalue":{"value":{"entity-type":"item","numeric-id":920841,"id":"Q920841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$1AF20767-3F0A-4AD2-B016-D0117508354A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02a7afaa43720bcf86b29d1d0d8112e49edf9bd","datavalue":{"value":{"entity-type":"item","numeric-id":3491304,"id":"Q3491304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$5D2902E5-6B48-46D0-B20A-C33C28579B0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824548$D9366E0F-81BD-4033-B240-53377FB82490","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b67fbdf7f6991631b9020b574edfd1efb7ee318d","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a155c2aa68aa20d83351fe2d6d8a07f26278ebe","datavalue":{"value":{"amount":"+0.8634147644042969","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":"Q1824548$2639DED5-2433-473E-841C-7CB650FC03C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68c03102fdf0c8a490873f97fb749c9a3e95932a","datavalue":{"value":{"entity-type":"item","numeric-id":4884975,"id":"Q4884975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd058e9ada3038658e937e465c32bcdc0c61b2e2","datavalue":{"value":{"amount":"+0.8621565103530884","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":"Q1824548$CA6FB4D6-9BE1-441F-B0FF-B064111FF533","rank":"normal"},{"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":"6ceb732a8b037a75457a3e825bbb2021e16a475a","datavalue":{"value":{"amount":"+0.8509806990623474","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":"Q1824548$EC7E0D60-331A-4D07-B03F-E4D122C7B968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f924058d29bcd6cb7914c8742a990493a65c2ef","datavalue":{"value":{"entity-type":"item","numeric-id":3033554,"id":"Q3033554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d51cf0613d7dac2d39f46230c4b15d808af1c453","datavalue":{"value":{"amount":"+0.8491218686103821","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":"Q1824548$BA10A47D-F79B-4726-B54B-5BEE106A901C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"984435967395ccff31160dc55a42ddfdc3ed12c6","datavalue":{"value":{"entity-type":"item","numeric-id":3813206,"id":"Q3813206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b238fea02160a97b15d4ccef6e23b9500cc4b4df","datavalue":{"value":{"amount":"+0.84861820936203","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":"Q1824548$FB33F91B-3E28-4FE3-A8D0-7E114DBCBCA5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A simple complexity proof for a polynomial-time linear programming algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_simple_complexity_proof_for_a_polynomial-time_linear_programming_algorithm"}}}}}