{"entities":{"Q1090601":{"pageid":1101353,"ns":120,"title":"Item:Q1090601","lastrevid":49073122,"modified":"2026-01-06T13:36:37Z","type":"item","id":"Q1090601","labels":{"en":{"language":"en","value":"An extension of Karmarkar's algorithm for linear programming using dual variables"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4008095"}},"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":"Q1090601$64E15AE2-3D83-4DAE-BF3A-4238F0F0BB34","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eef19f127422324279bb8fb0bc6f9a423b487d05","datavalue":{"value":{"text":"An extension of Karmarkar's algorithm for linear programming using dual variables","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090601$8FA016BA-B6E1-44CF-8B86-CB2CF4F0DAAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d4c84219e666fbb2f00b1b4a50f6daddebc9555","datavalue":{"value":"0621.90048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$B4907520-5FEF-4C82-AAD7-D62928F3EFB2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0e9a96b6c675d5a02c7c41e53876a477060e1be","datavalue":{"value":"10.1007/BF01840455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$3BE1546A-E1C3-4740-A13C-6C457848644A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce0cabc3c589adb96c46faf1b8ce022ce3270b5b","datavalue":{"value":{"entity-type":"item","numeric-id":173843,"id":"Q173843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$F2A004B4-38AF-4AE5-948F-B9C1B5B08220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b40eac81e304af2b445fac5720587cac79bd43f","datavalue":{"value":{"entity-type":"item","numeric-id":1090600,"id":"Q1090600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$217E18E9-ED30-4F44-957C-275E93B7F478","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$6184BC3A-60E5-40F2-B30E-9DFCCB283286","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1090601$FC92BB05-F6FE-4E26-BE5A-DB4C5AD0BF5B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bc2072fa0a48154888dd8bc278528d8dad603b3","datavalue":{"value":"The recent, but already classic projective algorithm of Karmarkar for linear programs is an interior point method, i.e. it generates a sequence of relative interior points of the feasible region, thereby reducing the objective value by a fixed factor. With an all integer problem the process may thus be stopped after a polynomial number of steps and the optimal solution obtained by rounding. The algorithm does however not generate dual solutions, of great importance in practice.    This paper describes a variant of Karmarkar's method in which both primal and dual solutions are generated, converging to optimal primal and dual solutions respectively. The method applies when the optimal value of the problem is unknown, and has the same convergence properties as Karmarkar's. Details on efficient implementation using OR factorizations indicate the complexities of the calculations involved at each step, and shows how extreme point solutions may be derived at each step with minor additional work.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090601$E5A56FAD-0171-415C-857F-F4BB52EE18B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$E62FE5CF-8FEE-479A-B20C-22B8AE97CE55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$C6270195-E842-47FA-864B-0DD77BED8DE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e038e5e16128fe63d90643b4c4804d63f3db1339","datavalue":{"value":"90C06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$5211640D-BB4C-4388-B6C5-128EE21C1B2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b09339c52564bfded86bbd1b8938f432a879010","datavalue":{"value":"4008095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$A1307B16-1396-4267-9B40-F24E07EEDE2B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1ecf978a28e5d1baefdbd10dbc4f102a6158a13","datavalue":{"value":"duality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090601$1488F86A-5EDB-445D-ADBF-7B8611854A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b35500a7c468744f587e5ccf40a6b4306d1ccec1","datavalue":{"value":"Karmarkar's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090601$D2ED5F76-3039-4BB3-B4EE-4565BF39A030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b4c1979f8b7f959fd6398735f8e34007babdd88","datavalue":{"value":"dual solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090601$EBEF6ACD-25D7-4388-A07C-81117EB57DF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f91519b287acc6a1005ea5e96094d83c66072d91","datavalue":{"value":"extreme point solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090601$58C80A87-5E0D-4E17-B6DE-99886B556163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59cb9229b6efcfbe683d694d8703f6bf29d18dc0","datavalue":{"value":"OR factorizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090601$131D8AF6-0EF4-4C98-84C4-C746AE1CDF24","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$240A9DD0-624A-43BA-B64B-DA511C114356","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":"Q1090601$915602F5-D1FD-45A3-A42C-727E688E24A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb743344b3478aef1355b552104e12d5037abb49","datavalue":{"value":{"entity-type":"item","numeric-id":5334750,"id":"Q5334750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$9410D673-25AC-4B09-AA92-97B908C91C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e4bd04b587c0758390f2e0ced121ecf83881a76","datavalue":{"value":{"entity-type":"item","numeric-id":3323698,"id":"Q3323698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$FE67AAEB-BCFC-4A1D-9191-AC1C95950D51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff2a07819c13da8dac0fa955bc9ec82b787d964c","datavalue":{"value":{"entity-type":"item","numeric-id":1152201,"id":"Q1152201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$3B9558EA-AF94-4A15-A5DF-32D685224455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d7e3ea5e32569f562d397c63044c70766a5448","datavalue":{"value":{"entity-type":"item","numeric-id":5185900,"id":"Q5185900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$1A46FA17-3330-4EC8-A81E-A3E3C7EC03D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5227fff9c76d1b9eb576c37228dc49eac8d0f210","datavalue":{"value":{"entity-type":"item","numeric-id":3942314,"id":"Q3942314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$3BA21C02-36A7-4AA2-82E2-540F334BD398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ad17a5108f1c837786bc97be9bbe643705f6c08","datavalue":{"value":{"entity-type":"item","numeric-id":4147870,"id":"Q4147870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$75EDF2CD-B2C7-45DA-8AD6-94A47A4BAAEE","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":"Q1090601$747850A2-35F1-4515-A1E2-6B482706338B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f335b2e50d6e1fafa5648baebb52ac146480150","datavalue":{"value":{"entity-type":"item","numeric-id":1226441,"id":"Q1226441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090601$37D6F7CA-D8C4-48B4-B21D-1F60FC5E244E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bdb401d3e5c1f93fcd8041806cf286088959c385","datavalue":{"value":"https://doi.org/10.1007/bf01840455","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090601$3D732E2F-C7A7-4A1A-8D24-20E59E54E251","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"65b98457400941c34a5f9dff06ee758754b6ee50","datavalue":{"value":"W1982967176","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090601$0E3BC4E3-7D15-4CA5-A14E-54AA3208A957","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98c3041f4914153ee8167df81b19c64656fa572d","datavalue":{"value":{"entity-type":"item","numeric-id":3780756,"id":"Q3780756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9039340dfd8505ed9ce71e3287ea59d962e4f578","datavalue":{"value":{"amount":"+0.8921710848808289","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":"Q1090601$7A6E7F49-8D84-45A5-BB13-73A7224DA92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d7901d203ed13ba74fc6ae64d6014adddd97a09","datavalue":{"value":{"entity-type":"item","numeric-id":1092808,"id":"Q1092808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a95c44b366b008f0890f61cc74485fac00390350","datavalue":{"value":{"amount":"+0.859943151473999","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":"Q1090601$C8A85A55-49CE-42EF-A2A9-F0F2CD841421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b413df6245644101801c3e8cc0b4beee92ebfd6","datavalue":{"value":{"entity-type":"item","numeric-id":3807877,"id":"Q3807877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c914012e8d4b03aa998d0b5e85a4e0f587bf641","datavalue":{"value":{"amount":"+0.8570343255996704","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":"Q1090601$42B2CA80-BCC8-4788-B57C-D49D3249A510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13f42c01fe580d995b66c9c548c3b56924c92c0f","datavalue":{"value":{"entity-type":"item","numeric-id":1824551,"id":"Q1824551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d6e2a0d0f0048b0417767b05fb26e2c9557ccde","datavalue":{"value":{"amount":"+0.8548976182937622","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":"Q1090601$AAFFEAB2-813C-4097-8CED-EDD3699172B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df31ebd4b1330471af69e0b8b837fd98dd7ef89b","datavalue":{"value":{"entity-type":"item","numeric-id":3496152,"id":"Q3496152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aa68f3c35a9ac9d358f22436293979bba053e6e","datavalue":{"value":{"amount":"+0.8445624113082886","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":"Q1090601$0D30BF52-3916-4AAF-991C-BC24ED446257","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1090601","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1090601"}}}}}