{"entities":{"Q715068":{"pageid":716917,"ns":120,"title":"Item:Q715068","lastrevid":51574709,"modified":"2026-01-18T20:50:13Z","type":"item","id":"Q715068","labels":{"en":{"language":"en","value":"On the power and limitations of affine policies in two-stage adaptive optimization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6093764"}},"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":"Q715068$EBB74970-FB93-416D-913B-754B5A7655D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7722d77b565a3e00bdd981607a47a976232dfc2d","datavalue":{"value":{"text":"On the power and limitations of affine policies in two-stage adaptive optimization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q715068$702868D1-130E-4BEA-945B-6EC7EF6D4FD7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fd521bdb77b88c251cf59cb679e00c6e488e3f0a","datavalue":{"value":"1267.90083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715068$391497FC-3BBD-4C73-8005-8BDEAED29EA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc0b3e86a8105371ec52533f98784df0ad9b43de","datavalue":{"value":{"entity-type":"item","numeric-id":623368,"id":"Q623368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$34E48B58-ED7E-4184-9F16-9E6A6119557B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad2eab65d87897920847ff75d5503474bf2e3b67","datavalue":{"value":{"entity-type":"item","numeric-id":689116,"id":"Q689116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$6A857622-611A-4CC9-95D4-BA4403F6D0E5","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":"Q715068$6FC10F83-5888-4FF4-9717-EAE6E2EF2A76","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"90cd4bb1c8ff7643cee66698544f44be0292260a","datavalue":{"value":{"time":"+2012-10-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q715068$1DE6A158-F5D2-4E74-BAA5-B15F712E9C5D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e79b91b2c0299d02c8e6a78439085c507b02a585","datavalue":{"value":"A two-stage adaptive linear optimization problem is considered under right hand side uncertainty. The statement of the problem includes e.g., set covering, facility location, and Steiner trees problems as special cases. The problem statement is rather general, however it includes a restriction of non-negativity of the objective coefficients. The power and limitations of affine policies in solving adaptive optimization problems is considered, where the term ``affine policy'' means that the feasible region consists only of solutions in form of affine functions of the uncertain parameters. A tight characterization of the performance of affine policies is given: it can be a factor \\(\\Omega(m^{\\frac{1}{2}-\\delta})\\) worse than full-adaptive solution for any \\(\\delta>0\\), where \\(m\\) is the number of constraints. It is proved that the worst-case cost of the best affine policy is \\(O(\\sqrt{m})\\) times the optimal cost when the first stage constraint matrix has non-negative coefficients. An \\(O(\\sqrt{m})\\) approximation algorithm, which is not an affine policy , is presented without the assumption on non-negativity of the constraint coefficients.","type":"string"},"datatype":"string"},"type":"statement","id":"Q715068$DF7BE27B-F326-44F3-B52D-B13E95C948CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6ffe289b9d980cec76d019204a667b111aa86811","datavalue":{"value":{"entity-type":"item","numeric-id":195460,"id":"Q195460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$9C8A1D95-1375-46DA-A3BC-73689087B9C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dade3bc82a2f7e555fdd92f6a7aa24c002fcafaf","datavalue":{"value":"90C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715068$DD12D08A-41B8-4C5F-8100-A089687A5E7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e564314c10fa5b362951b280af9f9f70fb290f3e","datavalue":{"value":"90C47","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715068$7FA4DA29-81BE-4780-BAA0-455D88678B4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bfba049ca6dfe73392c7887b7453c8e190905742","datavalue":{"value":"6093764","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715068$725D460E-F357-419C-A958-B707E8D1FF54","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87e0e22f581cd71cbecac448cd8596eb0b90e0d5","datavalue":{"value":"robust optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q715068$DCE5807D-1AFE-40EA-9CE7-AE92C6FFF74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d89edf7158c6bd7cefb72f77a0a77dd284a056a5","datavalue":{"value":"affine control policies","type":"string"},"datatype":"string"},"type":"statement","id":"Q715068$A552ADED-BB3A-403C-B17B-5470639B723E","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":"Q715068$82B7DAFB-376A-40E6-920E-AE47B8E702B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bfb5caeb4d3a76a96092ccca46195ecf566b8e01","datavalue":{"value":"https://doi.org/10.1007/s10107-011-0444-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q715068$799B981D-768B-4DD9-B154-87C9348BFFDD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"90e538e655473d0170a823fccdb6c6dc8f14221e","datavalue":{"value":"W2107968842","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715068$EB70AFC9-3D8E-4FAF-83AA-E7A5B664899C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"94982b33bb37f30885cf3c9e5b77bffa790860c4","datavalue":{"value":{"entity-type":"item","numeric-id":5266741,"id":"Q5266741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$7EA9018B-83EA-46E3-87F5-8881B5B0E603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c66382dce153f308c300d24c889aa2510050e011","datavalue":{"value":{"entity-type":"item","numeric-id":2492683,"id":"Q2492683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$45D82F97-61E2-4752-B35C-439B4706F32F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e77c1f90dd8ae1418bf5446f6fc71a5906099286","datavalue":{"value":{"entity-type":"item","numeric-id":1434080,"id":"Q1434080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$310F6DF9-C42F-4667-9CBD-49BA4DCF0607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdebec6ff73bb4dfe4e026880d3f5aab0f15d186","datavalue":{"value":{"entity-type":"item","numeric-id":995791,"id":"Q995791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$1196042D-4016-445B-A702-14D0A010F8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c60d3bddb93a95a42c0426b0a8c159627cc0df50","datavalue":{"value":{"entity-type":"item","numeric-id":5282256,"id":"Q5282256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$F3AA7859-FF74-45C8-9436-077863D8DD5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31715e36abeab0dd5a0bb0a85f168e06b5261723","datavalue":{"value":{"entity-type":"item","numeric-id":3169094,"id":"Q3169094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$4A927C96-2004-4879-890C-7524EB89F2A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93d4f508e3724efa042ed66fcc882002957a5b46","datavalue":{"value":{"entity-type":"item","numeric-id":5347915,"id":"Q5347915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$7B42F580-7A49-420B-B72F-3E240B019DF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a453e5312b91ce0526ccd36980c1c28aee54d34","datavalue":{"value":{"entity-type":"item","numeric-id":3169098,"id":"Q3169098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$4AA13064-16F2-41A9-BCEF-E42A5D9F4800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b505f0cac141b5bd69f045b6542066d70cca5dbb","datavalue":{"value":{"entity-type":"item","numeric-id":5429285,"id":"Q5429285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$4340EC13-09F9-4885-ABFA-66D7477EF6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8c1eacf180bf4d42c880ce516c80b5a77a5362f","datavalue":{"value":{"entity-type":"item","numeric-id":3541119,"id":"Q3541119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$9A6B11DF-53E7-41C7-9E05-2EF0C866E764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7b195250d317b51628ed2c749c9408f99e8ba21","datavalue":{"value":{"entity-type":"item","numeric-id":647394,"id":"Q647394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$F4A27CA8-8B22-4878-8742-B2020FE63454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"566a4c4f3c97d8a6fd92b6d27a58d1c4d1fe261a","datavalue":{"value":{"entity-type":"item","numeric-id":4181614,"id":"Q4181614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$73C7BAE1-FE32-4AE6-9EAE-B923DDAA3743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc70698dd6a38a5a5bb31f451d09bab426544ff","datavalue":{"value":{"entity-type":"item","numeric-id":4978992,"id":"Q4978992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715068$E417B7C5-859A-4B27-BC34-1305022FAA1C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"90d084d286d9d69ae13ca524f8ec19bac98d9403","datavalue":{"value":"10.1007/S10107-011-0444-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715068$672DD322-78CC-40B5-A5E7-4FAD9DF7D2F6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25eadf980e5bcfb55ab24f0b8874e5ad4f25fc55","datavalue":{"value":{"entity-type":"item","numeric-id":747776,"id":"Q747776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77cd3120107993a248d7d9da30831d4b8f176938","datavalue":{"value":{"amount":"+0.8892444372177124","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":"Q715068$F5247A62-06DB-41E8-908B-C8799AF096D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec1a252ae9bcd125bacf1a9b80560024b4a7f7b8","datavalue":{"value":{"entity-type":"item","numeric-id":5000650,"id":"Q5000650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9097ab67c5d8570ca6701b22726cff78f3d5fe79","datavalue":{"value":{"amount":"+0.8673772811889648","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":"Q715068$4D73C582-5D8B-4E37-B75B-DD75635E6476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f683f2c07696493a9e2d1c13054be4205387768e","datavalue":{"value":{"entity-type":"item","numeric-id":1753067,"id":"Q1753067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a93ea7f2c3379d54161df4ffde2a69ed68822b4c","datavalue":{"value":{"amount":"+0.8533750176429749","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":"Q715068$AF8C62E4-086B-42C2-B29E-9F520C6F372D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a528647f926966958c6681b5b6fe812e1ddfcb5","datavalue":{"value":{"entity-type":"item","numeric-id":2191764,"id":"Q2191764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b3cad1b7406438a0ff8cb6e8ec943e79ea76655","datavalue":{"value":{"amount":"+0.8246983885765076","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":"Q715068$F78E3E33-DB1C-4373-ACAD-B1ACC438469C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e4bdde775e72e3eda522d43212d7302db3153b0","datavalue":{"value":{"entity-type":"item","numeric-id":2830953,"id":"Q2830953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1000b5e3d393b3ed30b13762a68bba15f84df5c","datavalue":{"value":{"amount":"+0.8015463352203369","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":"Q715068$C4C4AA1F-9D03-40C3-9BE5-3E5FC1C53C09","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:715068","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:715068"}}}}}