{"entities":{"Q1319020":{"pageid":1329770,"ns":120,"title":"Item:Q1319020","lastrevid":47242834,"modified":"2026-01-01T02:49:33Z","type":"item","id":"Q1319020","labels":{"en":{"language":"en","value":"Finding an interior point in the optimal face of linear programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 549155"}},"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":"Q1319020$60D49144-9864-4BDB-8E50-CA11A97442F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9777f7cb50bfcddcd7f648c9d4e78f4243e7454","datavalue":{"value":{"text":"Finding an interior point in the optimal face of linear programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1319020$2F002B7A-63D6-4F3D-909A-A2243173F422","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a4c99435a0fc11bfab068d7f663a69c597927da","datavalue":{"value":"0803.90089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1319020$32E6F176-EFC2-4F9D-A5C2-B60288A4699F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f536dab5ad0c7760f50e98f9c06270ff72cc765","datavalue":{"value":"10.1007/BF01585180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1319020$C5A43C86-ABA7-4D2E-A98B-EBCB241F60B0","rank":"normal"}],"P16":[{"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":"Q1319020$48929FFD-BEC3-4778-B4DD-2E3D940E2C32","rank":"normal"},{"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":"Q1319020$C3CE3DF4-27C4-42E9-B963-904EA33336C1","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":"Q1319020$6322A950-BBCC-4452-A20D-8916DA37A120","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"474438facc06fb671d8e5448a17e8dde14fde7a6","datavalue":{"value":{"time":"+1995-01-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1319020$BD30B9D5-1851-4D4C-9EBD-ADBE47CBA6E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3666a864feb530c82004c58e6c966f986a8e4b46","datavalue":{"value":"Consider the problem (P): \\(\\min c^ T x\\) subject to \\(Ax= b\\), \\(x\\geq 0\\), and its dual (D): \\(\\max b^ T y\\) subject to \\(A^ T y+ s=c\\), \\(s\\geq 0\\). It is well-known that feasible solutions \\(x^*\\) and \\((y^*,s^*)\\) are optimal for (P) and (D) respectively iff \\(x^*_ j s^*_ j=0\\) \\((j=1,\\dots,n)\\). Let \\(\\sigma(x^*)= \\{i| x^*_ i>0\\}\\). The pair \\((x^*,s^*)\\) is strictly complementary if \\(\\sigma(x^*)\\cap \\sigma(s^*)= \\emptyset\\) and \\(\\sigma(x^*)\\cup \\sigma(s^*)= \\{1,2,\\dots,n\\}\\). The partition \\(\\{\\sigma^*,\\bar\\sigma^*\\}\\) of \\(\\{1,2,\\dots,n\\}\\) is an optimal partition, where \\(\\sigma(x^*)= \\sigma^*\\) and \\(\\bar\\sigma^*=\\{1,2,\\dots,n\\}\\backslash \\sigma^*\\) in view of the invariant character of \\(\\sigma(x^*)\\) and \\(\\sigma(s^*)\\) for every strictly; complementary solution \\((x^*,s^*)\\). The authors study the problem of finding the optimal partition and a pair of points in the interior of \\(\\theta_ p= \\{x: Ax= b,\\;x\\geq 0,\\;x_ j=0\\) for \\(j\\in \\bar\\sigma^*\\}\\) and \\(\\theta_ d= \\{(y,s): A^ T y+ s=c,\\;s_ j=0\\) for \\(j\\in \\sigma^*\\}\\). The authors claim that the optimal partition can be identified in \\(O(n^ 3 L)\\) arithmetic operations where the data in (P) are rational and \\(L\\) is their input length. They also propose a practical and (column) scaling independent criterion for identifying the optimal partition. Finally, the authors report computational results on the problems in the NETLIB test set.   For related work the reader is referred to \\textit{R. M. Freund} et al. [Technical Report, Sloan W. P. No. 1674-85, MIT, Cambridge, MA (1985)] and \\textit{E. Tardos} [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1319020$CB777048-E19E-4087-86E5-5A8E190329CC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1319020$ED41796E-6781-4B15-8AD2-C90FDBCA4626","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e57eb0f04fbb648f05571213d402813aa1125c31","datavalue":{"value":"549155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1319020$C782CB7E-5B93-488B-BBE6-327010BFB78F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b88f802da9cdb2e426336d98c1df285c99157b51","datavalue":{"value":"interior point","type":"string"},"datatype":"string"},"type":"statement","id":"Q1319020$398BAD92-D9EF-49A5-A43A-83D60A56A3DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a1202902e96d8c9d39db1f7f0c968390ffe4703","datavalue":{"value":"optimal face","type":"string"},"datatype":"string"},"type":"statement","id":"Q1319020$CE9F0BC7-5236-4330-9A08-7A5423C13715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"142996cc006eed97fe98ea111f719caed566b9f8","datavalue":{"value":"primal-dual methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1319020$D9AA8929-E203-4F2E-AC60-1D61A6EEC1F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"167ac98a8b728cda62959ff27f140d2e994c2b52","datavalue":{"value":"strict complementarity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1319020$B5D7932F-691F-457E-AF1C-0BAF44D92FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30b483fa984c937fc062aa1f034ae44f3188a3f8","datavalue":{"value":"optimal partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1319020$CB225723-35AB-4DBE-8B73-FFCCE0AB98FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6d49a43c08b100b2da6602674447e4ff15909eee","datavalue":{"value":{"entity-type":"item","numeric-id":167936,"id":"Q167936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$BF1CC55B-C18F-4C05-9A9F-EF1C6BEA456E","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ab3966d5d6e8667fc001b632fbfdec3e474c4efe","datavalue":{"value":{"entity-type":"item","numeric-id":23426,"id":"Q23426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$ECE1C30B-7044-407B-BD6D-9CE0B2A9BCC3","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":"Q1319020$39DC5C71-CBCC-48AC-87D4-A7D143CC487E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2eb0af7791d017d824c2b487dd670a9e2fa98ded","datavalue":{"value":{"entity-type":"item","numeric-id":1193520,"id":"Q1193520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$38327EA5-E978-4450-984C-B9A7DB99CAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ce45617c7ef75a9dddfcb1c30226591f0abc1d6","datavalue":{"value":{"entity-type":"item","numeric-id":4030926,"id":"Q4030926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$5445A2D1-D44E-4796-A783-AF24CBB35C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"643c8099611dd8ac161904ada1e6597f632cb72f","datavalue":{"value":{"entity-type":"item","numeric-id":4292667,"id":"Q4292667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$797BF447-303F-4FBB-9F62-0C2236CC2F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8192028b31a94e2d9fc25ae4d41631bb3314b88","datavalue":{"value":{"entity-type":"item","numeric-id":1321659,"id":"Q1321659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$646F5273-5BCB-4476-AA5D-1410DE3C0635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4b1a9efe3138ef518ab3b992a00c66ff905eeb7","datavalue":{"value":{"entity-type":"item","numeric-id":3236242,"id":"Q3236242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$70A1FB5C-5507-46EA-8B8D-14821E319E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5b87bc04fb15f455200776ce7465194aca7436","datavalue":{"value":{"entity-type":"item","numeric-id":3033554,"id":"Q3033554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$708AB711-96EF-484D-AA9F-6102570F52C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2fe4872882185c04ce0e93466dcf969ef3bc8e","datavalue":{"value":{"entity-type":"item","numeric-id":689124,"id":"Q689124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$CA4BE650-A98B-4BB6-A0FD-FD7A4337B999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7887a1dbd123c34a453ce09ae845890c9ba820dd","datavalue":{"value":{"entity-type":"item","numeric-id":1123139,"id":"Q1123139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$099DF216-55A0-4235-BDD0-BF9F4B4E1A97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06721624c441b54087b60fa7af61bdbc880573af","datavalue":{"value":{"entity-type":"item","numeric-id":4025897,"id":"Q4025897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$00115741-5083-4453-A9C6-F81C4496928D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb44ccd6b92800473fefc09ad6f3b633e4cf0f2c","datavalue":{"value":{"entity-type":"item","numeric-id":3140544,"id":"Q3140544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$8C6120BC-9A62-4F88-9427-B63EBD6015AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7687a2c040ff3812a1fc2b7dd0610e635b260aa0","datavalue":{"value":{"entity-type":"item","numeric-id":4286944,"id":"Q4286944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$3BA97C2B-CB94-4C8A-B184-30C069FF9266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d704b163797cf91f123edaacc228d2d912159b5","datavalue":{"value":{"entity-type":"item","numeric-id":1123121,"id":"Q1123121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$5A561229-4C5F-4110-83FB-00329E4F3B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53d400ae67354c276eb452acdccfbc71361c8b32","datavalue":{"value":{"entity-type":"item","numeric-id":1108927,"id":"Q1108927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$101A6D14-57D1-4123-A313-1F01949814BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$1F6EE5B3-1721-4467-8FDA-A3F5B6D7A4D1","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":"Q1319020$9570B3ED-B712-4B2F-9218-1BC39BF9F8D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2d5222dd09c659a98cfba98d37c0ecf2786f443","datavalue":{"value":{"entity-type":"item","numeric-id":4018391,"id":"Q4018391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$939B04E8-705A-4C40-8C2C-5A89BF4A5962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0645fdaa8941523699beeacef604bd643337295","datavalue":{"value":{"entity-type":"item","numeric-id":920841,"id":"Q920841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$E1EF637D-E88F-4213-9E8F-8E36E72BA439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666ed4fbb877e146ccdd8dce1c0d22c42c11b81a","datavalue":{"value":{"entity-type":"item","numeric-id":687096,"id":"Q687096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$DB4FC617-E15E-4F1F-873B-225EF81CED5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edfb1b7763a0c4062e90a20e69574676676fc93c","datavalue":{"value":{"entity-type":"item","numeric-id":2368076,"id":"Q2368076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1319020$E16F94DA-2BCC-4050-89FF-DD5A0C2771F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b5e5b8f31c7dcf39c9df3e682d2c6f68069f002","datavalue":{"value":{"entity-type":"item","numeric-id":1174842,"id":"Q1174842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe457893af922cca38dab220bc96786503a3562e","datavalue":{"value":{"amount":"+0.810556948184967","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":"Q1319020$CB6BAA78-7F30-46EA-9B76-3D0DC43758CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d19bfa64d464000c40cbe86adfe06e8710b8602","datavalue":{"value":{"entity-type":"item","numeric-id":5882391,"id":"Q5882391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cfdddb8a9f13db18dceb107768639a0ef4d1741","datavalue":{"value":{"amount":"+0.8095172047615051","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":"Q1319020$737D10DD-704F-4864-A551-21F01C04E81F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa44a4fe4d339fb9399e6159673fb9d094b278c9","datavalue":{"value":{"entity-type":"item","numeric-id":1961979,"id":"Q1961979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b630e314eefe3988cc064b7a1a0af4363ac90e3","datavalue":{"value":{"amount":"+0.7971282601356506","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":"Q1319020$BECA3381-F15D-4A5F-B442-12BFE3F7A013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce143ccc5c811375052fee38b54514c52f190d2c","datavalue":{"value":{"entity-type":"item","numeric-id":4025897,"id":"Q4025897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5ae056e32b7f1e5d7e052d4fb3a911103b8b91a","datavalue":{"value":{"amount":"+0.7889580130577087","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":"Q1319020$AA271E0C-1B80-4D45-8BE4-8FE9D9F5CA30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ff12b837f867fc626d2d92e64fd939c8aa6350c","datavalue":{"value":{"entity-type":"item","numeric-id":687096,"id":"Q687096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b70136d5ffd31e212f09e49e858e4739f722916a","datavalue":{"value":{"amount":"+0.7837537527084351","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":"Q1319020$BDAE8022-0718-46B3-A5D2-D5D8723D3916","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1319020","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1319020"}}}}}