{"entities":{"Q1950388":{"pageid":1961130,"ns":120,"title":"Item:Q1950388","lastrevid":51713615,"modified":"2026-01-19T15:40:40Z","type":"item","id":"Q1950388","labels":{"en":{"language":"en","value":"PASS approximation: a framework for analyzing and designing heuristics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6162390"}},"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":"Q1950388$2770E86D-7C5A-4909-9672-9DB65CF59821","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e8fe512e6079e0c5bae4eaff54640ddff54135e","datavalue":{"value":{"text":"PASS approximation: a framework for analyzing and designing heuristics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1950388$A4F62A15-8B7B-46EE-A698-83BE39EE4543","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"475e95dada0a9e2a8fe177a386b4677c47bcbc14","datavalue":{"value":"1298.90133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1950388$38D0E9C2-C0A1-462B-BD3D-35834F225F68","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c477bf762e94bbb5dc0264e8d37068f288152914","datavalue":{"value":{"entity-type":"item","numeric-id":423735,"id":"Q423735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$6A7284C1-8116-4C38-8647-BDE37E312863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce85e7f4152206ec385b698aa5837671d9203aaa","datavalue":{"value":{"entity-type":"item","numeric-id":614044,"id":"Q614044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$C6C06B9F-0B94-4797-9600-543B45A479F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0a10103d2ba783e47a71bc1d8056c5b62a2098c","datavalue":{"value":{"entity-type":"item","numeric-id":547288,"id":"Q547288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$4C3D383C-EC24-45E4-9A0D-1B0800BDB4D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4fbe35cb61496fa8363dcdb2d9d3a4d54bbef6e2","datavalue":{"value":{"entity-type":"item","numeric-id":6480586,"id":"Q6480586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$B80D3103-AC4E-42AE-9649-5215C21A2230","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":"Q1950388$B3310E54-23A6-4CE5-BF16-1013BB762754","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f1c659f2d5db271689f4e9c1eeccc577d11f193f","datavalue":{"value":{"time":"+2013-05-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1950388$89368A7C-E8BA-457B-AFB1-84B6A67DEA4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"206093948b30bc04fbf1b2819b9ebf3927a583be","datavalue":{"value":"The authors introduce a new framework for designing and analyzing algorithms. Their framework applies best to problems that are inapproximable according to the standard worst-case analysis. They circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. Given their parameterized approximation, called parametrized by the signature of the solution (PASS) approximation, the authors design algorithms with optimal approximation ratios for problems with additive and submodular objective functions such as the capacitated maximum facility location problems. The authors consider two types of algorithms for these problems. For Greedy algorithms, their framework provides a justification for preferring a certain natural greedy rule over some alternative Greedy rules that have been used in similar contexts. For LP-based algorithms, they show that the natural LP relaxation for these problems is not optimal in our framework. We design a new LP relaxation and show that this LP relaxation coupled with a new randomized rounding technique is optimal in our framework.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1950388$91A2EFF3-E5D3-426A-BEE5-509C158E57DB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e163e4f3415749f33672d8f8826866902fa1e334","datavalue":{"value":{"entity-type":"item","numeric-id":586527,"id":"Q586527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$5308947C-B20F-478F-9012-553C8265BFD0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1950388$D96F6063-ED96-44DF-9627-2DD19067E10E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5ee9a19fb5143b537dab57138b79f44e825fe92","datavalue":{"value":"6162390","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1950388$45117DC8-86D9-4137-A4AF-D4D964F8D5D1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1950388$B52E0326-9C07-4941-8868-32E74E301DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dc76359e1b247b8a96b03ef98bc894d41ad211f","datavalue":{"value":"facility location","type":"string"},"datatype":"string"},"type":"statement","id":"Q1950388$89341BF1-3E16-4AFA-8F06-E05BC365A4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49f11d8ab8cdf3d036152ef28bdda87e11fd46e5","datavalue":{"value":"sub-modular optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1950388$E1B9B7F0-2B65-4068-B1E5-A2BD36C2B265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"409420c906767f54dd647103a39d1b3310887166","datavalue":{"value":"display advertising","type":"string"},"datatype":"string"},"type":"statement","id":"Q1950388$C86E11FA-1ECC-4926-BB5F-CC9755C32C1C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"3e6e76231ab8404fa5530db100ab9a1a80b022e3","datavalue":{"value":{"entity-type":"item","numeric-id":20665,"id":"Q20665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$9A0070B2-8D4B-466A-9D67-5F3F44ED6707","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":"Q1950388$D63F0141-66A8-47F8-B82A-468DC2D8B647","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86ae5676520855863fec312e1a91f07d06aa31d6","datavalue":{"value":"https://doi.org/10.1007/s00453-012-9646-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1950388$E136BBB9-22F3-486C-B2D6-F92225D46C26","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5d58e9a0a6b7edd108fd0fe26193ea3d864e937b","datavalue":{"value":"W2180209872","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1950388$DF3769B1-7C2C-445B-B110-59EECA92AFD0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"853f3159c60b218168c9857596d8d7a6d846512c","datavalue":{"value":"Q101126194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1950388$104B56BF-6C86-464F-A08E-1F50B53BFAE5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4990a423f48f5b5a42e29ecad5fe35c7f764bc0a","datavalue":{"value":{"entity-type":"item","numeric-id":1296569,"id":"Q1296569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$5677D41D-C5E5-4477-9F30-17AC43B9C5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"715ff7d35ee08de7a3810826e5cbdbc4fb6bbbc2","datavalue":{"value":{"entity-type":"item","numeric-id":4845849,"id":"Q4845849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$CC6586D2-66B8-4A14-A78A-8640B96F5B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"671fc2186f91875a44e93a8640df028a0257ad79","datavalue":{"value":{"entity-type":"item","numeric-id":4135210,"id":"Q4135210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$304B3105-7954-4AE5-8B82-609D8258A8B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$D813392A-26FA-44E4-92EC-AAB8CDB4FEA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b1eb70dba78268f355cadba4f42de2bfbf92559","datavalue":{"value":{"entity-type":"item","numeric-id":2931368,"id":"Q2931368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$79534F10-90A1-4AFB-BAE8-6ED0EA15BEE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7060c9bd383afd85d1ea8c7530020cb641da0776","datavalue":{"value":{"entity-type":"item","numeric-id":3638872,"id":"Q3638872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$3762A85E-F93E-49FB-A6B7-0D8EF52DBA90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5a07bbe12f8d0413febfe03352bb2b37ef84b73","datavalue":{"value":{"entity-type":"item","numeric-id":1604213,"id":"Q1604213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$805D45ED-2C36-44DB-B133-9AC7B0B9A30D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caf641c5760e5adf4dc6bf4d962143669aec9c9e","datavalue":{"value":{"entity-type":"item","numeric-id":4411280,"id":"Q4411280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$8520D6ED-30FB-4F10-935E-0915BF89367E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$83E7BC05-ADE4-4ACA-B1B7-08F9DFB45E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c837d56e04962823c1d7c934cd015e72d540d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1588908,"id":"Q1588908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$8817A741-2078-40B9-8B89-A1A7B8CF662D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5f1aa9294846cde8376d837af26608b9f41054","datavalue":{"value":{"entity-type":"item","numeric-id":2941641,"id":"Q2941641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$CA13C44A-662B-4064-B892-1F7F55CD8FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5909b9a9933c2bb0d9cc45055fda97cfd37d42aa","datavalue":{"value":{"entity-type":"item","numeric-id":5501190,"id":"Q5501190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$73FB17B6-443A-4DA3-8B61-878E11D57B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51caf26d32988cefbe5dd48ca13263418169e039","datavalue":{"value":{"entity-type":"item","numeric-id":3549607,"id":"Q3549607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$13E9D0E9-0F3B-4030-B1F6-E9D5023737BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d10bec1389020353d0d555f9995ec233a91d501","datavalue":{"value":{"entity-type":"item","numeric-id":3583576,"id":"Q3583576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$E9BDC32F-81BE-434E-A1AE-42D5FC514305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b34a246508428ac62689a0f6e17e01f841a8d923","datavalue":{"value":{"entity-type":"item","numeric-id":3002782,"id":"Q3002782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$67DC9A69-B936-45FD-BBFB-9305886C00FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bef2fa029dcf19bf5fe6570d4108cb1ee4292ff7","datavalue":{"value":{"entity-type":"item","numeric-id":2819597,"id":"Q2819597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1950388$FF2E0502-1BC6-4532-98CA-6853BF0F3546","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f00af506d4453e3ac19bf364fc2ed3299067ee59","datavalue":{"value":"10.1007/S00453-012-9646-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1950388$008C0FF7-8A7B-43E9-839F-D66D8CC229C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1889fcc2c8a3b3eab8d0a840cf78054aa0dc8262","datavalue":{"value":{"entity-type":"item","numeric-id":3638872,"id":"Q3638872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"945e47e043325ae0ab19e08e5f3e8b17475fe9f1","datavalue":{"value":{"amount":"+0.992624282836914","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":"Q1950388$195C494A-B62D-4F3F-91E9-A6164B13BBE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2fc63f5e90084cf55ec3e5723732d17b62ce601","datavalue":{"value":{"entity-type":"item","numeric-id":5443801,"id":"Q5443801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e217cc3cb7c22b7815c3c680049fa861a03fa42","datavalue":{"value":{"amount":"+0.7593759298324585","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":"Q1950388$A3F28374-8237-46A2-88AE-673ED04D9793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"249f1b1535cda1519391dba4829ddbededfb134d","datavalue":{"value":{"entity-type":"item","numeric-id":1884771,"id":"Q1884771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65effa2fc296efff039cc117a0b69f5dad17cb0f","datavalue":{"value":{"amount":"+0.7448105812072754","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":"Q1950388$E21531C3-517D-4A3E-8D54-B513224B9B0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56f4f792d5e93d7cee06bf2054df1ca250034b32","datavalue":{"value":{"entity-type":"item","numeric-id":4250234,"id":"Q4250234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"900803434fbb8bb24f78134f7baea82ed7e15485","datavalue":{"value":{"amount":"+0.7445600628852844","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":"Q1950388$C98E2B26-4ED3-47F3-AD98-4CC26D49F77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cd90ddf7decd4e8696c5e180f955a35a076eb92","datavalue":{"value":{"entity-type":"item","numeric-id":4263705,"id":"Q4263705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"900803434fbb8bb24f78134f7baea82ed7e15485","datavalue":{"value":{"amount":"+0.7445600628852844","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":"Q1950388$F9E82AD9-4BC2-4AE6-968D-669A66C09DCF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1950388","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1950388"}}}}}