{"entities":{"Q909582":{"pageid":911430,"ns":120,"title":"Item:Q909582","lastrevid":49357786,"modified":"2026-01-07T00:49:39Z","type":"item","id":"Q909582","labels":{"en":{"language":"en","value":"Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4137533"}},"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":"Q909582$B63B2479-1E2F-44BA-A79F-85A87A1E9390","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7496cf161c4fa35101ac584a2c571b20157943ef","datavalue":{"value":{"text":"Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q909582$3E96209D-E404-499D-9F96-0AFBE030A773","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d80df80e11674b941add8ce3643505966a06cda","datavalue":{"value":"0694.90075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909582$13888BE0-0417-4AC9-85EF-078E315C270F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b16404a927a922f75dac3dee7b5dd57e36288e4a","datavalue":{"value":"10.1007/BF01585740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909582$FD528310-193C-4D84-8CFE-0468489B8399","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cce947c11bd7fd58c83190d519ef228f357b0b1f","datavalue":{"value":{"entity-type":"item","numeric-id":233532,"id":"Q233532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$E34E16E4-A218-4B74-9B6E-C096C61ADE5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ed74cd8b4711628a611438aeb686bfc6e5f9f03","datavalue":{"value":{"entity-type":"item","numeric-id":751507,"id":"Q751507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$2EDBA711-18D3-4587-8285-A7D65DBD75A8","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":"Q909582$4113CF24-622A-4A54-A918-5FF5CF7B8099","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":"Q909582$1BD8E094-EBAF-4433-B251-007223C6D1C8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"24fbf68f5f1d9b7bd745af6de081a1656a9de105","datavalue":{"value":"\\textit{E. Tardos} [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)] was the first to present a polynomial algorithm for solving LP problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand sides and the cost coefficients.    This paper extends Tardos' results to convex quadratic programming problems of the form  \\[  (P)\\quad Max\\{c^ Tx-(1/2)x^ TDx:\\quad Ax\\leq b,\\quad x\\geq 0\\}  \\]  with D being a positive definite matrix. A polynomially bounded algorithm for solving (P) where the number of arithmetic steps is independent of c and b, but depends on the size of the entries of the matrices A and D is developed. The algorithm finds optimal primal and dual solutions to (P), if they exist, by solving a sequence of simple quadratic programming problems using the polynomial algorithm and by checking feasibility of linear system in time independent of the right hand sides.","type":"string"},"datatype":"string"},"type":"statement","id":"Q909582$F6CF8FAF-FA2C-42AF-9B1A-173CE73F0B2E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909582$4605301A-BCDC-45F6-8978-520780A133A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909582$5B9E2A7C-45AB-4938-9F73-FF3293C188FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909582$C59FBCAC-5008-43E5-97F3-452A70E7094F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1da70fe61c95219ff7bed8997906d3e79436db03","datavalue":{"value":"4137533","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909582$F802ACBB-AD26-4153-BF8A-E06C4195B05B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2530ad92bf57ad49c3a9ab88a408f45d644be85f","datavalue":{"value":"convex quadratic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q909582$CB959177-C9B3-427B-BE4E-DA6D3EC94A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee685f23b1e08316d9db5047055129abc94696da","datavalue":{"value":"polynomially bounded algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q909582$58FDAB64-2E7A-40BE-B513-4E0491478037","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e479dc24524beac34ffccb3b6e1377016a539d34","datavalue":{"value":{"entity-type":"item","numeric-id":485484,"id":"Q485484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$2A62F721-4408-4F17-9F13-210FBC1E125A","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":"Q909582$234C7DF0-87B9-443B-981D-DAD8368BDC30","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9287cbcfd545c8a0b609b7e99b58e99a8903c00","datavalue":{"value":{"entity-type":"item","numeric-id":4180171,"id":"Q4180171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$D417B9AF-6474-4425-A2B2-1CEAE771F2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef41c217abc948f435065435efff70b4de349af","datavalue":{"value":{"entity-type":"item","numeric-id":5334744,"id":"Q5334744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$767465E3-360D-4831-AD47-727B4B1E25BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c1431029d095176d0255ac422aa2994290421c8","datavalue":{"value":{"entity-type":"item","numeric-id":3863664,"id":"Q3863664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$C0661323-F82C-4878-B4F4-E39EDD568513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24aba1a5440b2b4c99fc157e4e513d4da249b6aa","datavalue":{"value":{"entity-type":"item","numeric-id":3284267,"id":"Q3284267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$CD38C8A4-AD1E-48DA-BE22-EFC4FF914E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81e7bae91edd4ef61e8a20980708dc8cf33337fa","datavalue":{"value":{"entity-type":"item","numeric-id":5653804,"id":"Q5653804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$8DD6D0B1-C9B0-454E-881A-4D2B81B4230B","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":"Q909582$00147E5D-1C48-4487-AB48-D1DEAA9E1509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$D530AA90-A5B9-4677-9E16-970410B7C927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8634671064abab94a7b8dbe7f85bfc42274b7db2","datavalue":{"value":{"entity-type":"item","numeric-id":4770776,"id":"Q4770776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$78EE19E7-1722-4995-B0B2-A233BB957523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"731e99376e8702c5d355c7d2ba0ddb139c20b787","datavalue":{"value":{"entity-type":"item","numeric-id":3899825,"id":"Q3899825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$B1FE824D-9858-4DC4-8A84-B4DF96131D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51a2d782cb3555aee32b8b11c56161420d6249be","datavalue":{"value":{"entity-type":"item","numeric-id":4143047,"id":"Q4143047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$3B83A21C-BE47-4B0F-A422-A5B8FF80B8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b290b3db3f847e0f1cb275f225ebdd148d96e5a1","datavalue":{"value":{"entity-type":"item","numeric-id":3873927,"id":"Q3873927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$6C534FA3-67B1-44B6-9139-D80988A45DC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b606a9aed93b16e925ed609c45da68462d53c66b","datavalue":{"value":{"entity-type":"item","numeric-id":761341,"id":"Q761341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$069C0A1E-DD6C-4944-A324-A8D2C363459F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aea04970626c2b6a6205a53b4ddfbe1134bb9c2","datavalue":{"value":{"entity-type":"item","numeric-id":3030579,"id":"Q3030579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909582$C93CCEAE-E29B-4E13-B368-4F2B0034DF81","rank":"normal"}],"P1643":[{"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":"afb581c0d1198a8e56397edc0116907cb8d2a83d","datavalue":{"value":{"amount":"+0.8558999300003052","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":"Q909582$80F81486-026B-4AF5-9954-8A87EB34E101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a19578f6547234f5d5385bc8576873d08900ceb1","datavalue":{"value":{"entity-type":"item","numeric-id":4383982,"id":"Q4383982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdcbf6c901518cd3b2c069d872602122f9587de9","datavalue":{"value":{"amount":"+0.8287585377693176","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":"Q909582$B4492CF0-5D21-4E8F-8DDE-C532A09C0D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"115d89b341340137f5c668bc0d6478684f8a24c5","datavalue":{"value":{"entity-type":"item","numeric-id":3320129,"id":"Q3320129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d707d475d953b8d95a4278eba63f6bf4db28ee9","datavalue":{"value":{"amount":"+0.8283435106277466","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":"Q909582$BBB3AE72-9072-4DBC-B6EF-2535CB207F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d8758c4df5276738d171494c2038d15bbb73c2d","datavalue":{"value":{"entity-type":"item","numeric-id":2016445,"id":"Q2016445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff3baae062a9b3c3981bba68ff9d47b30462d9ce","datavalue":{"value":{"amount":"+0.8271097540855408","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":"Q909582$8EB031BD-2769-48D7-BE0A-BFBDF405B8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f6b22c5e67a1b3d8d647e707f7dbb08cd245919","datavalue":{"value":{"entity-type":"item","numeric-id":1804355,"id":"Q1804355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"211986a82667e87a7ca2ad14fe487972df412e09","datavalue":{"value":{"amount":"+0.8223680257797241","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":"Q909582$8AEE393D-401B-4894-A5EF-9CC813997B34","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:909582","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:909582"}}}}}