{"entities":{"Q1103522":{"pageid":1114274,"ns":120,"title":"Item:Q1103522","lastrevid":66139323,"modified":"2026-04-12T07:48:28Z","type":"item","id":"Q1103522","labels":{"en":{"language":"en","value":"Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4053340"}},"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":"Q1103522$BE93A211-5C21-4311-9562-0A67F374ADD9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77e68f761a3872c9b1913b697ffabc42e211d96f","datavalue":{"value":{"text":"Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103522$1072915C-6E49-4E6A-840C-BE0BD216E86A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a26d6b5a1f9b69ba2cc878b152c2ff4bf560dc80","datavalue":{"value":"0645.90048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103522$52B14C90-DFE8-480D-AAF1-0A2232C28A01","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c2d9486f2e5258fbf8b0884e6560bdb13d3c71e5","datavalue":{"value":"10.1007/BF01580729","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103522$128EA73F-94F6-43EA-B013-C3514CA1EC24","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"389c681e6859e96625810538dab4d8964ec9e5f5","datavalue":{"value":{"entity-type":"item","numeric-id":233995,"id":"Q233995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$FEB4E88F-4DE5-4D60-9903-298BA329F5ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cc3cbe474fb83a006cca698eaea2c0246a45088","datavalue":{"value":{"entity-type":"item","numeric-id":173876,"id":"Q173876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$BB129766-20EB-457C-BA19-69574372FE7C","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":"Q1103522$AFBE826A-A8B6-49F3-B69B-00440C3B2181","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1103522$0389A68F-0B7C-4A2B-9D40-4B8018DEFAFC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b400caf1b910400cc995a37c6102d97a0e2d58f3","datavalue":{"value":"Considered is the linear programming problem minimize \\(z(x)=c^ Tx\\) subject to \\(Ax=0,\\) \\(e^ T=n,\\) \\(x\\geq 0,\\) where A is an \\(m\\times n\\) matrix of rank m, \\(x\\in R^ n\\), \\(c\\in R^ n\\), and \\(e\\in R^ n\\) is the vector with all its elements equal to one. It is assumed that e is a feasible point, i.e. \\(Ae=0\\), and that a lower bound \\(z^ 0\\) on the optimal value is known.    The authors give variants of Karmarkar's algorithm for this problem with unknown optimal objective value \\(z^*\\). These methods combine an earlier approach of the authors for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds for \\(z^*\\) using dual feasible solutions. It is also discussed how to compute an initial lower bound for the optimal objective value and how to transform a ``standard form'' linear program into the form given in this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103522$C113C547-62D0-4D89-A6BD-6DE3119DEB19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103522$B709FC10-5E7C-4684-9657-50BF52079C45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103522$34926ECC-AC24-4321-BFE1-3DA06CE98170","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07c172a072cdf25af4c191e023e411c20c3cfa23","datavalue":{"value":"4053340","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103522$F27001C7-503A-4906-AA8E-176D15670B75","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90c19b7fa6f8c3370763709c150d2361327c4c09","datavalue":{"value":"variants of Karmarkar's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103522$5AD71707-5FF6-4C90-BF66-AD06F28FEB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0856d28904406a72a4564123d2d3e51e6ed69176","datavalue":{"value":"improving sequence of lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103522$7ECF791E-85AA-41A8-A51D-446C7CAF7E8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce3a7f71d945dbc679e5c475ba3d6bd546f190a3","datavalue":{"value":"dual feasible solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103522$7E45ACC7-EEC3-41B8-9CAF-11F7B5767CA5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b3fae90bb7453994aebaa95521e955f916797091","datavalue":{"value":{"entity-type":"item","numeric-id":587437,"id":"Q587437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$6FE95AF8-8707-48C0-A70C-50A843A00971","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"46123b0cb91c1cb13d108cbdd9f84d42b23a22a6","datavalue":{"value":{"entity-type":"item","numeric-id":5974493,"id":"Q5974493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$62999C87-CB3A-4113-88AD-A8CD1D6931C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"704a143f6521b56a4a365794d3b7b9cd7a30f3f0","datavalue":{"value":{"entity-type":"item","numeric-id":13285,"id":"Q13285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$1333A995-5E7A-4D4A-93C8-05310CE8B1EF","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":"Q1103522$7D0DC241-49D3-4537-8812-7002E71F9D55","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":"Q1103522$68B5DF8D-69D1-4880-8030-4C99AD0F6FFB","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":"Q1103522$E93E6F8E-3550-47DA-BE26-3DF0DBC53C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cf97f66a175a7c268c5c13b2c5ed046f45699b3","datavalue":{"value":{"entity-type":"item","numeric-id":1108926,"id":"Q1108926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$6C7B3B98-EA91-43DB-8FB0-39F9683E56AE","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":"Q1103522$E8802F23-B949-440A-B634-902E3FC95E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f33474b8f611a02da9b0aac769013d9428a081","datavalue":{"value":{"entity-type":"item","numeric-id":3936097,"id":"Q3936097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$B0D04C61-86CA-449E-992C-3988ABE8842F","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":"Q1103522$31D69438-931E-41E0-82CF-5F72B130BA76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62094c59468b9a46577364118260416e48286faa","datavalue":{"value":{"entity-type":"item","numeric-id":3773690,"id":"Q3773690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103522$C660474B-56E2-4CBF-91E4-C0DC4C390B7C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46d9e12ae039bf2b73050fbe79e8f59a999c435d","datavalue":{"value":{"entity-type":"item","numeric-id":3767120,"id":"Q3767120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0251d6862007eafccab9a186318b3536c6239da","datavalue":{"value":{"amount":"+0.8571605086326599","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":"Q1103522$4F521044-13A5-420C-8F6B-33ED59684219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f6b7069b34e835698b2d4e575b6f48439a597d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819909,"id":"Q3819909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5505003111e88011d3bcb81a2f42bd857e516784","datavalue":{"value":{"amount":"+0.8481556177139282","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":"Q1103522$38A82504-FBC0-4A1E-AB77-60528A408366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebcb2db50b54fb6162b1457a5b2c689fda376004","datavalue":{"value":{"entity-type":"item","numeric-id":3030578,"id":"Q3030578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b0af6a0674936797df3f821eb9310bc97c670df","datavalue":{"value":{"amount":"+0.8226522207260132","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":"Q1103522$B5049020-A3A9-4DD3-A1F0-98163CD79CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d11619b5d4fb9e7bbb007ce3ae9933c10611c287","datavalue":{"value":{"entity-type":"item","numeric-id":1090601,"id":"Q1090601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0db6c18b5a8d9ce86f92b630daaa7886af79d108","datavalue":{"value":{"amount":"+0.8093149662017822","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":"Q1103522$4FAA4AA2-86B9-41A6-8214-ECAECFF26B83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"693f3b85828d7e40aac47c0f3cae6fa91028ec28","datavalue":{"value":{"entity-type":"item","numeric-id":1108926,"id":"Q1108926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3341e0219a745db9b44d71d86816496b597aff64","datavalue":{"value":{"amount":"+0.8045336604118347","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":"Q1103522$A91C484B-670E-40A2-A6D4-2D7F384D3672","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Relaxed_variants_of_Karmarkar%27s_algorithm_for_linear_programs_with_unknown_optimal_objective_value"}}}}}