{"entities":{"Q1612911":{"pageid":1623651,"ns":120,"title":"Item:Q1612911","lastrevid":68044689,"modified":"2026-04-12T21:03:52Z","type":"item","id":"Q1612911","labels":{"en":{"language":"en","value":"Linear programming, complexity. Separation and optimization."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1796611"}},"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":"Q1612911$5D6CEEC7-FED8-4BCA-874C-2AB14CB75CC4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"644234c24a29f34ec2b67373e4c3c447c95c6b49","datavalue":{"value":{"text":"Linear programming, complexity. Separation and optimization.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1612911$E946353E-474F-4DA8-87DC-E3DEB027F77E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8fcb183d483ba2e88f24e65fff4d2cce4d2c868a","datavalue":{"value":"1010.90041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612911$246E20C0-EB82-47CF-A5F4-37F9ADE23304","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3f0402d8a7fa11b3a8941089edab76117ab371d7","datavalue":{"value":{"entity-type":"item","numeric-id":229877,"id":"Q229877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612911$87EF16C2-DC5D-4B17-B562-A1454571507D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"984f89431fd3bd278c430e81f3345c06d05910ab","datavalue":{"value":{"time":"+2002-09-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1612911$AE91DAAD-2605-4F5C-9EE6-8521890392B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf25b8ba7f3deb357ee92dfdee95ff0a3e0c902f","datavalue":{"value":"This book introduces to the complexity analysis of algorithms, measured by the amount of time needed by an implementation on a Turing machine. This amount of time is expressed as a worst-case function of the size of the problem, which is the amount of memory needed for storing it.   The first chapters introduce the model of Turing machine and classes \\({\\mathcal P}\\), \\({\\mathcal NP}\\), and \\({co \\mathcal NP}\\) of problems. A first application is the Gauss factorization algorithm for matrices; it is shown how a modification due to Edmonds allows to make it polynomial. Then in a second part the author deals with linear programming, analyses the simplex method, and then the ellipsoid method of Khachiyan that proved that linear programming problems could be solved polynomially. The book ends by analyzing the relations between separation from a polyhedra and optimization of a linear cost over a polyhedra.   Unfortunately the book gives no indication on improvements of interior-point algorithms that allowed to decrease the estimates of complexity, and also to obtain efficient implementations. But this said, the book is a very useful introduction to the basic questions of algorithmic complexity, and should be helpful to many students and researchers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612911$1918BD81-E587-4591-BD57-234F724A9543","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eca2c7badf47f0ef6622a64b0bdd3bda904b5ece","datavalue":{"value":{"entity-type":"item","numeric-id":588442,"id":"Q588442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612911$E952A224-F786-48DC-A5E7-BD8303D8917E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"30e0158d39e8dcc6ee00ca7b3ae626e5899d5903","datavalue":{"value":"90Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612911$F0C1C454-3DA2-49A6-A6D7-A280B9E9E42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e47044a48934462ae67daab4b129c466ca4197f5","datavalue":{"value":"90-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612911$8115642F-7C5E-4E53-B037-194412C8B673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612911$E39C8CCE-F18B-4011-B3D2-599FDDD42415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612911$BF462BE2-A6C9-46DF-84C4-559FBCDCA33E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05ce447b1f59ff8c080a95c85a643ed3db18054a","datavalue":{"value":"1796611","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612911$AD2B124B-E846-4D02-947D-3F60721F70F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4780b02cfc7bc35a586062e3271a9f52fa94f067","datavalue":{"value":"complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612911$68CE5AEE-C138-4FB1-B2C9-9CB0DC937450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612911$86430C86-2BE4-4BC7-87DB-463A2725AFAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612911$F8863287-A321-464A-A395-74E1041EDC47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"599981ae0f13000555cdfbe3e563d6ac043c85d5","datavalue":{"value":"ellipsoid method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612911$6C2A063B-2FD7-4C11-B643-A69CFF2A64FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93077cc6db36e07d535db7c75a2f03eb0743cd04","datavalue":{"value":"algorithmic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612911$A4B728E9-D293-4663-9B67-3808E1CECC79","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8ddbf263f302694b90f2fb268b20c4fe4f56512","datavalue":{"value":{"entity-type":"item","numeric-id":496664,"id":"Q496664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612911$33D73CC8-5732-4DFC-924D-BACD05B7314F","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":"Q1612911$726C380F-4F8C-41CB-BC12-73357A2FDF43","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"112330a358623fa5fb94a42fb7ea7e6e6d882d8b","datavalue":{"value":{"entity-type":"item","numeric-id":3976517,"id":"Q3976517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4e3bc03d763585a623d677335c4f64dcc84b13c","datavalue":{"value":{"amount":"+0.9146065","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":"Q1612911$B8220DB2-5F90-451D-8163-F97025CBE0A3","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":"c4e3bc03d763585a623d677335c4f64dcc84b13c","datavalue":{"value":{"amount":"+0.9146065","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":"Q1612911$018BC42D-D107-4138-BBBC-E223E8F28F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e37174c9f8b5499620baf1bc04b5f9dceb4d826","datavalue":{"value":{"entity-type":"item","numeric-id":1924066,"id":"Q1924066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f68c5b48aacbd462611a4b51a2521e878f2a2fc8","datavalue":{"value":{"amount":"+0.91410315","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":"Q1612911$CBD1E3AE-5D3B-4205-8166-591067589FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e144c9dfaed028d7d62909b3afb8eb64a59c515a","datavalue":{"value":{"entity-type":"item","numeric-id":3929385,"id":"Q3929385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a93a0fa481bf1f6e97639bbee40db1b2d2338f5","datavalue":{"value":{"amount":"+0.9117545","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":"Q1612911$60DB1DA3-2D97-4EC9-B751-C24676ACEDB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da2bcb9b4fbfe7895402336b5f375c484e689707","datavalue":{"value":{"entity-type":"item","numeric-id":3694971,"id":"Q3694971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b961401d566ef6b49812f6d39cd820a2995da67","datavalue":{"value":{"amount":"+0.90108156","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":"Q1612911$688EF136-2DA8-4121-8C4C-2E4E1FEE3F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37cd5acf4a0cd271d971f07ad997690f829a3a70","datavalue":{"value":{"entity-type":"item","numeric-id":4435806,"id":"Q4435806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df1cfca3f3e49c98dda845bc3c27ac32d2c31aed","datavalue":{"value":{"amount":"+0.9009229","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":"Q1612911$B59E72C5-2DFB-4F56-A994-1E0C6CAFA04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7adb982301a587bf4e9c4d4507678674b5914bf6","datavalue":{"value":{"entity-type":"item","numeric-id":935681,"id":"Q935681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df1cfca3f3e49c98dda845bc3c27ac32d2c31aed","datavalue":{"value":{"amount":"+0.9009229","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":"Q1612911$C8A3EAFE-B19C-4CB3-82FC-C4FBB41F02AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0c6716901340f04851496ade5656ffcd5e50af9","datavalue":{"value":{"entity-type":"item","numeric-id":4221106,"id":"Q4221106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ee7f5e6e2b543d9a326e9cd19a57b84d9ee624a","datavalue":{"value":{"amount":"+0.90091753","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":"Q1612911$94AA9094-FB47-497F-B1FA-DC4F80AD22B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"264c09fc9b999768d5368e1853a4617d70556d8d","datavalue":{"value":{"entity-type":"item","numeric-id":5946779,"id":"Q5946779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cf2af21cd07294f67a70ba63c0fa4fb0b102e31","datavalue":{"value":{"amount":"+0.9008248","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":"Q1612911$EE12C60C-E80E-45CD-8AE3-882956E1E197","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear programming, complexity. Separation and optimization.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_programming,_complexity._Separation_and_optimization."}}}}}