{"entities":{"Q1095025":{"pageid":1105777,"ns":120,"title":"Item:Q1095025","lastrevid":69627264,"modified":"2026-04-13T08:18:24Z","type":"item","id":"Q1095025","labels":{"en":{"language":"en","value":"Karmarkar's algorithm and the ellipsoid method"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4027160"}},"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":"Q1095025$F3AA7C8D-6BF5-46D3-A621-C2D51F2F71B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee7e198b9d35747aca13cfcd613876af16a590c0","datavalue":{"value":{"text":"Karmarkar's algorithm and the ellipsoid method","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095025$7D93745A-32AE-490B-91C7-DF7E0FEBCF7F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6350fa11f9fb11dc43e4add2974a1e2eefa452a7","datavalue":{"value":"0631.90035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095025$67F9AF57-AE25-447F-B903-08B990E94D62","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6179635716facbc9b17c80f079f9a2edb59d4ff3","datavalue":{"value":"10.1016/0167-6377(87)90016-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095025$80450F5A-24D4-4FB9-BE20-DD37621B5CD6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f722a9d373eb3dc93c3a37caf61c6de6dd0a5d2b","datavalue":{"value":{"entity-type":"item","numeric-id":173845,"id":"Q173845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095025$A71B20F2-1796-4719-A6B6-E660AA71F88E","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":"Q1095025$5B77EA43-2A84-41F5-A500-5A5C11CE39E3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1095025$E7329A4B-73CC-4DC0-82D2-E1E5140F6605","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"314cb37caa1422b825de5a7cbe0bae7f5aac36c7","datavalue":{"value":"We show that Karmarkar's algorithm and the ellipsoid method are closely related. At each iteration, the potential function used to measure convergence of the primal solutions in Karmarkar's algorithm correctly characterizes the logarithmic volume of an ellipsoid that contains all of the optimal dual solutions. As the potential function declines, the volume of the ellipsoid monotonicly shrinks to zero. These ellipsoids can be used to determine the optimal basis for linear programming. Conversely, the relation of these two algorithms may lead to an efficient implementation for the ellipsoid method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095025$ACC9AE14-7C3F-4AE4-89D9-0EB2223ADA5F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095025$569A3A9A-0D7A-40D1-8CE5-44CE07C6B819","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"78f25c5fdcfe1864cc0d1f595ae96e19e1f332e9","datavalue":{"value":"4027160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095025$DD5690A9-3068-4237-94F3-1DEBFFBA56A8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b6a58e2a9394fd06861b8a07dab6ded3b3f11c","datavalue":{"value":"primal and dual programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095025$5038ADEF-728D-4E5C-884D-E5B782B238C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b35500a7c468744f587e5ccf40a6b4306d1ccec1","datavalue":{"value":"Karmarkar's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095025$CDADDAD3-62AC-4A44-8A3B-BB559C6EED12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"599981ae0f13000555cdfbe3e563d6ac043c85d5","datavalue":{"value":"ellipsoid method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095025$F8A1AFC2-A639-4173-9247-A593DC39F4FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1aa595b274bea57dadabbb84752e337f20f78ed","datavalue":{"value":"potential function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095025$29F33D7B-69AC-48E8-B1CF-BFC513CD23F1","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":"Q1095025$941542EF-52F5-4102-989E-0D364C10D316","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7d44481c6e54d3d6387a618e2091140b648b8a2","datavalue":{"value":"https://doi.org/10.1016/0167-6377(87)90016-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095025$91C2C5F7-B3B0-4070-8B93-0CC4991DA57D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a14de22f5a584fae8c705f2e293ed24b7804413b","datavalue":{"value":"W2061711344","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095025$82FB8CBD-9248-4EA0-8D02-9A2CE61820DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2aa250e3b281d881c1358be098bb79318ac3c5","datavalue":{"value":{"entity-type":"item","numeric-id":580191,"id":"Q580191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095025$42E902A6-71FC-4044-A808-CC38454D4C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec5d67a059af5f0c1d2a9b85106bace80a574daf","datavalue":{"value":{"entity-type":"item","numeric-id":3705220,"id":"Q3705220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095025$5B97647C-4305-455A-9886-82141F87768E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095025$483D08BC-6923-446B-B68E-2BA209985096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"829faa41c190acbc5fdd381e9fdce642e3ddbc3e","datavalue":{"value":{"entity-type":"item","numeric-id":3767120,"id":"Q3767120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095025$BCF435AE-F5BB-4AEC-8E1F-2FA01982E9DE","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":"Q1095025$C2ECF11B-F949-4AEC-B966-1F86216BC8A6","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":"Q1095025$8FF40805-0950-418B-B1AA-204C065E1C77","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":"Q1095025$2CFD9D19-B1C7-4E8C-AE14-D4ED9CD83B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b365497a35d2bc4f523f5dc7d8ba065391e6222","datavalue":{"value":{"entity-type":"item","numeric-id":1090601,"id":"Q1090601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095025$BE6932E3-1B81-4497-B0C1-6573EDCDAD3D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d800a90037844626300a7265afb405192cf97bbe","datavalue":{"value":{"entity-type":"item","numeric-id":5479693,"id":"Q5479693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3d26aaab126a134d27962dcc2cf91d79d573fb2","datavalue":{"value":{"amount":"+0.8322696089744568","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":"Q1095025$15197A3A-1399-4A72-84C6-963DCDCED136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9c3197e1af0132ad3b46a6c5cb6fd7af64f3955","datavalue":{"value":{"entity-type":"item","numeric-id":3818123,"id":"Q3818123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b4ac55c390bf536363aa2dc2469dcbe0c2d3aaf","datavalue":{"value":{"amount":"+0.8322111368179321","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":"Q1095025$E98D141A-8966-4027-9D75-F2750BF0C5D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14b68e042f6ea8a741c2caa914b0c0c29377d158","datavalue":{"value":{"entity-type":"item","numeric-id":4881038,"id":"Q4881038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8b9f52ab537d4f7e79babe482a4f004ddac9d15","datavalue":{"value":{"amount":"+0.82550448179245","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":"Q1095025$F0F8B5FC-D1C6-416F-95FC-E95BB53C5B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b5a9432ac9464134dc017a055efc5c8d1bf9bd2","datavalue":{"value":{"entity-type":"item","numeric-id":1813834,"id":"Q1813834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da691a08d5f8e935577a6880e97e3f5ae7add00","datavalue":{"value":{"amount":"+0.8245874047279358","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":"Q1095025$1456E1A4-5FE9-4E26-BB4A-8DE1A2B243B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3152a9028d159a89c56d9a9fec45d654be180b95","datavalue":{"value":{"entity-type":"item","numeric-id":3737217,"id":"Q3737217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0eb2a9ef3a6707c78e980c9814ae693f4418c580","datavalue":{"value":{"amount":"+0.8217757344245911","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":"Q1095025$481EAE80-C058-4245-BFF9-11755576CC42","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Karmarkar's algorithm and the ellipsoid method","badges":[]}}}}}