{"entities":{"Q1196720":{"pageid":1207469,"ns":120,"title":"Item:Q1196720","lastrevid":66840240,"modified":"2026-04-12T13:13:03Z","type":"item","id":"Q1196720","labels":{"en":{"language":"en","value":"A polynomial method of approximate centers for linear programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89475"}},"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":"Q1196720$340B0C36-C53B-4545-8EA5-B8B1B1D07B62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"81bfa5850e625cb9de0464f29546abdce70e3e95","datavalue":{"value":{"text":"A polynomial method of approximate centers for linear programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1196720$51DC5B3C-195F-499E-B789-FEB2166DA817","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"04b719556d671d0f4461e87d307f2aef20805dd5","datavalue":{"value":"0771.90067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$097D4436-CD9D-4911-83F7-55BE7CE0C5B3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a061537a5ebe1d87b4dab515e51c294a672aacc","datavalue":{"value":"10.1007/BF01586056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$FD3EBCB6-16B7-4C07-A8B9-6E9E67397595","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e832e7deba703a47cd00f916492617521d6c95d","datavalue":{"value":{"entity-type":"item","numeric-id":181239,"id":"Q181239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$D3260E47-5B37-446F-B2B1-4C86643F2A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41f9223d98cb24b639031125780dec8c6cadee10","datavalue":{"value":{"entity-type":"item","numeric-id":172146,"id":"Q172146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$3F7A9CB0-4E4C-44D4-9003-04DD425A1551","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":"Q1196720$545D7159-4DD4-428D-8311-DB25C1F81056","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1196720$99ACC10B-FEF6-45CF-BDEE-B81A41CBE077","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44373666a31e481b952eb039f35dc84f55df4d98","datavalue":{"value":"The introduction and the last section illustrate clearly how this paper relates to the literature. The authors give a general picture of the stream of research that evolved from the publication of the Karmarkar method in 1984 and resulted in the development of a number of so-called interior point methods. Such methods are discovered to be strictly interrelated. For example, in a previous paper of the second author, it is stated that ``the projective algorithms for a phase II problems are all the same''.   The method proposed here is essentially that of \\textit{C. C. Gonzaga} [SIAM Rev. 34, No. 2, 167-224 (1992; Zbl 0763.90063)] and hence belongs to the category of path following methods. So, where is the contribution? It is in the convergence analysis. Providing a simple and elegant proof of the polynomial complexity of the method is the main topic of the paper.   The method has its limitations --- the feasible regions of both the problem and its dual must have non-empty interiors and the coefficient matrix full row rank (although this latter hypothesis is claimed to be not essential).   It is interesting to note that, in contrast with the promise of developing, in a subsequent note, some trickery that will lead to a record complexity, the method is deluding, when it comes to practical efficiency. The remedies are in the spirit of other already proposed methods.   For the high quality of this paper, it leaves the desire of refreshing novelty in either the approach or the class of problems dealt with. This stream of research seems to be close to saturate its potential. Fortunately a revival of interest toward nonlinear optimization is emerging within the field of interior point methods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196720$DD069572-202B-451C-8DD4-4021BBD08C0A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$356457DF-F06C-44DD-A2F8-D011C0EF98D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$9CE343E2-504E-458A-8B1D-24ACBDE31734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$D2867A0B-D735-4FC6-A16D-F3139C079768","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e58b70f10cde24f607f15152f9ce92edf3851dd","datavalue":{"value":"89475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$3AA10E14-56F3-49F6-9862-A09092AED67D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5463f8cb67c335ff66aa835d1eefbd219fa938e5","datavalue":{"value":"interior point methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196720$073B4456-DC0C-4F46-B50B-3BFECD57925E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0f813d0ce285171db1d97ff429f7ca5c19af5a7","datavalue":{"value":"path following methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196720$53ECCBE3-3FA1-4C87-9F82-09D2A92534E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6915992d79cfb515074cc438de9b3e413b98cfe1","datavalue":{"value":"convergence analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196720$35EB1288-9D02-4E24-A4B9-4E81613D0205","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"708b2b589282eab472d79d9085b9ef37c660fcee","datavalue":{"value":{"entity-type":"item","numeric-id":1062947,"id":"Q1062947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$DDA6C99F-65EC-40BE-BFD7-886FC6D7BE3F","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":"Q1196720$A8DEB945-592D-4B46-8D23-A52E7E3D8644","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":"Q1196720$DB9F4326-7BDD-4A74-9CE6-8757EE428B4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97b410fc86eee244f2d98582a1b142583a7c111f","datavalue":{"value":{"entity-type":"item","numeric-id":1196717,"id":"Q1196717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$98D49654-34C3-4CE0-A1DC-5E72A421830A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c633d9447e5d986230e2957316f8249514ca99d","datavalue":{"value":{"entity-type":"item","numeric-id":3030578,"id":"Q3030578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$06A7D6C9-C875-4EA4-BDA6-D0A82ECED703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d4a4f4dd932bd775f3d25a9110ed67c05d2f39a","datavalue":{"value":{"entity-type":"item","numeric-id":1094330,"id":"Q1094330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$1599E1D0-14F0-4185-9885-81881EB2C327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6d1ec9843c65861c97c28bde17d5f7b4cd3ee00","datavalue":{"value":{"entity-type":"item","numeric-id":5583564,"id":"Q5583564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$D10ACDF5-DFCA-4453-884D-4F9E82C53C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77b18dae1feab607aebf734b4872f30598593d59","datavalue":{"value":{"entity-type":"item","numeric-id":1177228,"id":"Q1177228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$566855C0-B148-40C9-B552-91B3915BE015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a4ed6006cba17f406781b62d8980af79fac4266","datavalue":{"value":{"entity-type":"item","numeric-id":3026741,"id":"Q3026741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$186F4E3B-CF44-4FF6-A015-DD4A52E20502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc638ffebcb99d48a431c67bd26d5debe11f9452","datavalue":{"value":{"entity-type":"item","numeric-id":2638936,"id":"Q2638936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$D8EC2A15-AD43-4B6E-9E6D-4AB76E1BEC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"125b97ff4bd170911cb27bc3ec0bca267816290d","datavalue":{"value":{"entity-type":"item","numeric-id":1814590,"id":"Q1814590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$C20EA127-4237-4C01-87AB-29AF143B94E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0209ef92cabf53ae3926e0cab7b04653ec4e5b40","datavalue":{"value":{"entity-type":"item","numeric-id":5540119,"id":"Q5540119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$946CB88D-095A-4AE2-9AC8-93508D2B55DA","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":"Q1196720$D10719C1-90E0-4932-8FCE-38DE5D0EE3BE","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":"Q1196720$EC0C6429-0B60-468E-A3CF-3A4EBF0EC7DF","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":"Q1196720$FF21F6ED-5605-4CC2-BB64-3788EC4A87EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d0e15d44a052d847195b741f77140c09425c45b","datavalue":{"value":{"entity-type":"item","numeric-id":3677069,"id":"Q3677069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$D81623D8-1218-4301-BFE5-F76D4EA34B17","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":"Q1196720$94D27673-7300-48E9-9860-1C8FE29264E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b2a7f66c1dacac691d1b1fc0d251d5a8dcbea26","datavalue":{"value":{"entity-type":"item","numeric-id":1114587,"id":"Q1114587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$060B06EE-D302-48D0-B2EE-EB5320E805FC","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":"Q1196720$B7EED89D-87D7-46AB-98E0-540D49A9241C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe09442c45daf3a6b51c358a7949ac67a755ae55","datavalue":{"value":{"entity-type":"item","numeric-id":3211107,"id":"Q3211107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$57E212CA-ADA2-48C1-AA25-34763A9B38B0","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":"Q1196720$03097FB7-7F1C-4585-8331-619FC35932DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a975d39735d0d10d92ac745a75752a43e0af022","datavalue":{"value":{"entity-type":"item","numeric-id":581231,"id":"Q581231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$E5F2B18C-0783-4EF6-A7CD-106426899185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25515025605026b71d4eb503f056ec378cc64045","datavalue":{"value":{"entity-type":"item","numeric-id":811360,"id":"Q811360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196720$A516EEFF-3169-42EC-9B8C-DBB3CDD391B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f1c4b18384a0cd6b8b7cde37f93381fe74ef1a9","datavalue":{"value":"https://doi.org/10.1007/bf01586056","type":"string"},"datatype":"url"},"type":"statement","id":"Q1196720$5AA919B9-7394-4E07-916E-3B3F7E431F6A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2ca7cc79367edf5369871778e1b7a08c56a3ccde","datavalue":{"value":"W2013162809","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196720$7C1069E4-1D6A-4F02-80B4-5C513DB709A7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c11a140916293c95abfba2cd8bd11bc7386b4b54","datavalue":{"value":{"entity-type":"item","numeric-id":4945429,"id":"Q4945429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0a86635ade856818c185931cfc024ee81884c60","datavalue":{"value":{"amount":"+0.8068023920059204","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":"Q1196720$F5F43460-76E9-4282-8E90-142744210DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf5a5e5f8af7f315c4fc0de434cbb62a543ed873","datavalue":{"value":{"entity-type":"item","numeric-id":803041,"id":"Q803041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0a86635ade856818c185931cfc024ee81884c60","datavalue":{"value":{"amount":"+0.8068023920059204","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":"Q1196720$5364E208-0061-46C2-B0D2-274555B2A9B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b67fbdf7f6991631b9020b574edfd1efb7ee318d","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5dce6de833c2341dee278ca0338718d774cfb90","datavalue":{"value":{"amount":"+0.8061794638633728","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":"Q1196720$86BEC780-C991-4A7B-86ED-797294434E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d97294c747d78ab75d5109af3fa110c4522fa168","datavalue":{"value":{"entity-type":"item","numeric-id":3150491,"id":"Q3150491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b63d3d2f98a7a400764a9df2c5da61437a966502","datavalue":{"value":{"amount":"+0.8044832944869995","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":"Q1196720$A1B793E2-1AA5-4523-9D37-2F24639C89A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fba30de7ad568fa3a46e8211c8dd3f2363205f28","datavalue":{"value":{"entity-type":"item","numeric-id":3484625,"id":"Q3484625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06d30100b42877baf35c6d376f4ebe2236123e71","datavalue":{"value":{"amount":"+0.8034264445304871","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":"Q1196720$361EBD50-AF8E-43A3-9C00-D5AD64F43BFD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial method of approximate centers for linear programming","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_method_of_approximate_centers_for_linear_programming"}}}}}