{"entities":{"Q920841":{"pageid":922689,"ns":120,"title":"Item:Q920841","lastrevid":42767184,"modified":"2025-07-10T13:44:00Z","type":"item","id":"Q920841","labels":{"en":{"language":"en","value":"An algorithm for linear programming which requires \\(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\\) arithmetic operations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4164541"}},"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":"Q920841$C40C839F-86CE-4EED-B9F4-BB6D0A8727F1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"84b7dbd8213ae7db2694f5bd92f52baddb955baa","datavalue":{"value":{"text":"An algorithm for linear programming which requires \\(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\\) arithmetic operations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q920841$225A5C5E-3D0D-4A64-A7BC-7ED8473EB6C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2ff69096874b5f1abdec169e71a8ae0eb94970e","datavalue":{"value":"0708.90047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$AE1DE8DD-5F95-422B-8B80-B1E631673082","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f102d2b1e4aca848f9e2e091d0bfe7af32b34daf","datavalue":{"value":"10.1007/BF01580859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$C4236C1D-6F87-4711-8081-901370B07774","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8de4a6f713c83ebac2233da0ff14b109d2f769d","datavalue":{"value":{"entity-type":"item","numeric-id":687083,"id":"Q687083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$32F66DAA-B586-4452-A142-EFE4D3409E46","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$73640BB5-0154-4BB5-8DDB-60480C45892B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q920841$3A4BC26F-0307-4EED-A259-2B13EB73E96C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"37376ea8ca303d666145aaa3de00268579cdbd04","datavalue":{"value":"The author gives an algorithm for solving a linear programming problem \\(\\max \\{c^ Tx\\); Ax\\(\\geq b\\}\\) where A is an \\(m\\times n\\) matrix. The algorithm employs the idea due to \\textit{J. Renegar} [Math. Program., Ser. A 40, No.1, 59-93 (1988; Zbl 0654.90050)] and proceeds by constructing a sequence of smaller and smaller polytopes which shrink towards the optimal vertex. At each iteration the algorithm moves from the center of the current polytope to the center of the next one by minimizing a linear function over an ellipsoid. The total number of arithmetic operations required is \\(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\\), where L is bounded by the number of bits in the input; thus the algorithm is faster than that of \\textit{N. Karmarkar} [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] by a factor of \\(\\sqrt{m}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q920841$D6F9D4AC-C38B-4E2C-9552-CEB49493B6C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$2410709A-46DA-4CBB-9CA7-A8278869BD70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$0990AE0F-4F33-4B94-A804-DD0C44139D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$7A9DD2A8-FEC8-4094-8749-501CA4AEC131","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a415ea970aa75a00734257bb53cbd082bbcfd979","datavalue":{"value":"4164541","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$DD07BFC5-6A05-4351-9B37-DB9D3EDEAC37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q920841$328D1C93-5477-4E4C-8EB2-C73D893A7FE7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a6ba53c58e0084a9f17d607fb0ad639f8cc8b0b7","datavalue":{"value":{"entity-type":"item","numeric-id":277136,"id":"Q277136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$77275474-D42C-4730-B5EB-AA23B29F88A4","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":"Q920841$DA4E115A-00DB-4206-8EB8-47E9292A0713","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9981dd68041bb8d98775cd35e426d994858a3017","datavalue":{"value":{"entity-type":"item","numeric-id":3824098,"id":"Q3824098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$A8BDD15F-CB2A-4CB3-9312-FD9E5EEAF148","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$F29D4296-DC5F-4701-85EE-1E8F1C9C06E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c790a28a23b5ecff99b272336c89700604ca255","datavalue":{"value":{"entity-type":"item","numeric-id":3254327,"id":"Q3254327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$FDC13859-74FA-4A5A-B2A0-7A539AF5DD85","rank":"normal"},{"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":"Q920841$2EDD3289-8FC1-4DA0-85E5-88449E7E522A","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":"Q920841$E19D26C3-8300-4A06-A3ED-E7B035136C9E","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":"Q920841$1FD3DC61-74E4-400A-9F20-AE625790133C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9f55cf5e4350fa88146f09cb8d2dc407e283322","datavalue":{"value":{"entity-type":"item","numeric-id":4057472,"id":"Q4057472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$03113082-67F6-492D-B5D4-A28FA2FF82E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b4a3c5e894623ed6c86b2d00f23c20c5ccdee6c","datavalue":{"value":{"entity-type":"item","numeric-id":5674306,"id":"Q5674306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$DDCCB323-8C10-465E-A050-E40837D0641F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8f76d12b5270ab1f1d52373edaeeb1caf4d81e","datavalue":{"value":{"entity-type":"item","numeric-id":4105489,"id":"Q4105489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920841$961D948F-BF27-484A-AD0F-0EB702B48D7A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1399b3f3af993647229ec6dc9cc2faed519e222e","datavalue":{"value":"https://doi.org/10.1007/bf01580859","type":"string"},"datatype":"url"},"type":"statement","id":"Q920841$CC922FD1-5338-43AB-B1E3-B5FE61E03822","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c611159229099e06330ea13dc8790334e247919f","datavalue":{"value":"W1993982015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920841$D49A5BA7-E55F-4937-9AEC-D7BCC658F03D","rank":"normal"}],"P1643":[{"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":"33022eb80e83c221e4ac98ff924f3ce415227a8c","datavalue":{"value":{"amount":"+0.8861072","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$9FB65C4D-742B-4866-A0AA-485291F8F543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06974a5d4ac0174eb3c5eedf4be9586d29fe8589","datavalue":{"value":{"entity-type":"item","numeric-id":4702310,"id":"Q4702310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbe177aa47daca2f4673dae426304798b6c07046","datavalue":{"value":{"amount":"+0.8783381","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$7227EBE7-E6A0-4588-904C-E051BECAAD9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e795f571d2a900771039e316b7ba3e28c5d1f0d","datavalue":{"value":{"entity-type":"item","numeric-id":756930,"id":"Q756930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c7af57a1c71d3c9e61b56ecbf22175d29042fa1","datavalue":{"value":{"amount":"+0.8779439","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$BBB9BD0E-2212-4785-BFC9-3580DC788092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f821d581bbb16020c376e08e3529b90ebeedcb10","datavalue":{"value":{"entity-type":"item","numeric-id":3200887,"id":"Q3200887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab5c3da6c2af5a67a88106ab50635216d41cc44a","datavalue":{"value":{"amount":"+0.87084496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$1DBBEFB0-1F48-4AF3-8AD3-E1A95FD6FF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5319a0c2e18a8bc01e043ac5a0a2844f5061fbe","datavalue":{"value":{"entity-type":"item","numeric-id":2368076,"id":"Q2368076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08d70fdc6f642bdf465275e8050977cf7284aa92","datavalue":{"value":{"amount":"+0.8604432","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$513D6CF5-5CCD-428B-8F31-EF011833EF97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d54367ab2174754878f5d59fb520cbdce1444fa8","datavalue":{"value":{"entity-type":"item","numeric-id":3976779,"id":"Q3976779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd7d5415afcce7b27e82631f218ff4ed77b4cfa","datavalue":{"value":{"amount":"+0.85753167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$04A08C03-E6F8-48AF-AA5F-E76923EB15C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73080160cc61c11fe9799d9c955055f3d1bf4c00","datavalue":{"value":{"entity-type":"item","numeric-id":1962975,"id":"Q1962975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd7d5415afcce7b27e82631f218ff4ed77b4cfa","datavalue":{"value":{"amount":"+0.85753167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$971C45CD-8BE4-41D6-9272-682FC49D42F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"809a127874bc2e8c3c6954f11daaec81cb1b976b","datavalue":{"value":{"entity-type":"item","numeric-id":4382745,"id":"Q4382745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac49de054fefecfa2f65208270b27f6fca7a9d34","datavalue":{"value":{"amount":"+0.8549725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$F1652825-64F0-4FCD-BCAA-01D74EF24FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4bb7598e5b7869d7d222d412ec33ac41b9011e6","datavalue":{"value":{"entity-type":"item","numeric-id":2639770,"id":"Q2639770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a0d648e41b0542a812edb65bce9b9aa08f46de2","datavalue":{"value":{"amount":"+0.8509859","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q920841$75FD2F9A-DCB1-4C68-BD5A-FB42A45EFF08","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:920841","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:920841"}}}}}