{"entities":{"Q2768049":{"pageid":2778788,"ns":120,"title":"Item:Q2768049","lastrevid":83187686,"modified":"2026-05-07T06:33:40Z","type":"item","id":"Q2768049","labels":{"en":{"language":"en","value":"The Lagrangian search method"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1698942"}},"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":"Q2768049$F4EAB6D4-A584-4AA1-8BE7-E1CAA442C9F5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e3a5bc93cdc523d1d3b40e28fe277877760825b","datavalue":{"value":"1007.90050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768049$8E95D156-1B6A-479F-BD46-1312D562CC87","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a67346d411f734cd9a7ec9d4c529e93c54b8e8f","datavalue":{"value":{"entity-type":"item","numeric-id":982650,"id":"Q982650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768049$AD00F389-3563-4E0A-8BC6-D6E855141B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8112a4884ac488e222bb031fe5d75202a7b6dcb","datavalue":{"value":{"entity-type":"item","numeric-id":389952,"id":"Q389952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768049$36003C72-5B65-4705-BDE7-FED86E9F706C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1f8512fdc779578a6ed7cea489dd7591a33e2b50","datavalue":{"value":{"time":"+2002-10-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2768049$041AD5DB-9053-4164-A0E8-3360B8735473","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768049$BC6C9E1F-0E03-4364-BBA9-7102E75CFB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768049$C461025A-B483-4E0B-8D7E-61CFF1BA421F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768049$C04566A3-5829-4618-A2B8-5022BB080EB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"29cbf0869a94c39816500b2fc5690691be3d7bf4","datavalue":{"value":"1698942","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768049$C0E5FF95-7699-4938-BD5F-1CB22702687D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a59e0c1eb51c50ee8b2be5656da8a2be878f5f1","datavalue":{"value":"Lagrangian relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768049$6CDB50A3-291B-4B4C-BF19-B2873E261FD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0796bfee61e96aabe25244e310cd0c5157f8ba9f","datavalue":{"value":"positive linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768049$1ED1E6E8-2F31-4C03-83D3-DD71DA5ADD6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9d9df214c6fc201e3492fc82e0f92f4e25cd888","datavalue":{"value":"approximate solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768049$A8F0F5CE-9272-4C06-9B60-E87C4982DC1F","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":"Q2768049$10BD991F-B861-4499-ADD8-DD3C7FC31D10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4f30bcce42c948535ffc75a176bb6e433a49240","datavalue":{"value":{"text":"The Lagrangian search method","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2768049$307B33D1-6A06-495F-9744-8B7D2AA650BC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2a04e8a3fff3d9b0916538f5e9465d664d2a6f4","datavalue":{"value":"The authors present techniques to derive algorithms for combinatorial optimisation problems that can be modelled as extensions of positive linear programs. This work is based on results for fractional covering and packing problems. A Lagrangian search method is developed to deal with the extensions. It is shown that for poly-bottleneck problems a relaxed approximation solution is found in \\(O(\\operatorname {polylog} n/\\varepsilon)\\) steps. The problem of global routing in gate arrays is presented as an example. Other examples are mentioned.NEWLINENEWLINEFor the entire collection see [Zbl 0968.00020].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768049$DE399A7A-9B24-4F6F-9739-B2FB39F51BCD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebec3fead859bfe042f90942bb009137165d63bc","datavalue":{"value":{"entity-type":"item","numeric-id":297048,"id":"Q297048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768049$088A50B1-0E8D-4FD6-896F-6D9C58B9EC3F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c39ae42686ed133ff3b40ac4967795ba0abb7d2a","datavalue":{"value":{"entity-type":"item","numeric-id":1315429,"id":"Q1315429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7307e710dc735b6da47a8f4da45db9b72b07973","datavalue":{"value":{"amount":"+0.7766720652580261","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":"Q2768049$A57F1752-093D-4EBD-8082-D06F348BCB1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3b4756f5f450f1f0281ffca5196fa65ef922234","datavalue":{"value":{"entity-type":"item","numeric-id":4342969,"id":"Q4342969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7307e710dc735b6da47a8f4da45db9b72b07973","datavalue":{"value":{"amount":"+0.7766720652580261","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":"Q2768049$3FB17E8C-34FD-4E40-8DDA-F16807588A7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7fdb14e9b4664bbc067955ef6e9e6aad64fe410","datavalue":{"value":{"entity-type":"item","numeric-id":5920487,"id":"Q5920487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b72e8824990cd0ef3905ad0367eac0a5b2bcc16","datavalue":{"value":{"amount":"+0.7714480757713318","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":"Q2768049$B1D21D00-E843-48ED-91F8-7D6443544ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fbd2cd1659aca2cbcc616ba20e920bf8ec99464","datavalue":{"value":{"entity-type":"item","numeric-id":4848416,"id":"Q4848416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1ca2d5fde47936864a04648baf784e184e2bc24","datavalue":{"value":{"amount":"+0.7711923122406006","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":"Q2768049$B6F728EF-08F2-43B1-81F3-3E26B64BAAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d85a70522727f113696156bc95f0f84846c09307","datavalue":{"value":{"entity-type":"item","numeric-id":3815115,"id":"Q3815115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1ca2d5fde47936864a04648baf784e184e2bc24","datavalue":{"value":{"amount":"+0.7711923122406006","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":"Q2768049$5CF27D06-0D63-45D2-BB07-DCF0111D0586","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Lagrangian search method","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Lagrangian_search_method"}}}}}