{"entities":{"Q5896869":{"pageid":7937208,"ns":120,"title":"Item:Q5896869","lastrevid":55976530,"modified":"2026-02-21T16:47:55Z","type":"item","id":"Q5896869","labels":{"en":{"language":"en","value":"Improved PTASs for convex barrier coverage"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7290981"}},"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":"Q5896869$2BFA462A-9DD0-42E3-8DB6-63A9356B9C7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"315ffa33b09d6b7a2ae8160b9ee4762b0e1b98d6","datavalue":{"value":{"text":"Improved PTASs for convex barrier coverage","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5896869$4739CF51-2CCC-4883-94A6-1053BA2F4D57","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"045ed1bdd2af495f609e0be49c08a123ce46ffa4","datavalue":{"value":"1477.68464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896869$7A2CD7BA-70CB-494C-B125-7A12886E249F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a266d729c395220c0c1ce9741b7a6ad65b6115d8","datavalue":{"value":{"entity-type":"item","numeric-id":390162,"id":"Q390162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$3230BA7E-F6AE-44EB-85E2-EA3799776E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35bc7f911719e7e39a341f40f86cea16ae495e48","datavalue":{"value":{"entity-type":"item","numeric-id":827308,"id":"Q827308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$A3C8D660-D18A-48B2-8D64-20940C0F67BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53d696d6a24b567dd930581104732f1204294d8a","datavalue":{"value":{"entity-type":"item","numeric-id":827309,"id":"Q827309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$6AFBEF4D-CCDC-4A70-B979-935E80B383AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5de52448e04f050e5b9f069b1a18cc236956934","datavalue":{"value":{"entity-type":"item","numeric-id":364842,"id":"Q364842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$959E0AF4-0E25-439A-AB24-568D879C0B17","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$A38027CE-D9AE-45E3-853E-B06594AB1131","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"28000f86d5331c096188ef3a8388c83c359f78a7","datavalue":{"value":{"time":"+2021-01-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5896869$07596D5A-71D5-4E3B-8B0C-89BCD1F99E41","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75902ef351b2970acb599dbb7be85c7dd661b554","datavalue":{"value":"Consider the problem when one uses mobile sensors to protect a region by monitoring its boundary and detecting intruders. Then, given \\(n\\) sensors in the interior of a planar connected region \\(R\\), we can consider the problem of moving the sensors to \\(R\\)'s boundary to form a barrier in the sense that every point on \\(R\\)'s boundary is covered by one of the sensors. The objective is to minimize the total travel distance of these sensors. In this paper, the cases where \\(R\\) is either a circle or a convex polygon are considered. A PTAS for the circle case is presented and it is explained how to overcome the main difficulties that arise when trying to adapt it to the convex polygon case. The proposed PTASs are significantly faster than the previously proposed ones. Moreover, the proposed PTASs provide efficient solutions to problems that are equivalent to the circle-restricted and line-restricted Weber problems. Thus, the efficient PTASs for these Weber problems are also devised.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896869$C4F7F568-7411-44FB-8A25-49ACCEF53C11","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7e53786640a962176e9d0bea3688ff978e73b3e4","datavalue":{"value":{"entity-type":"item","numeric-id":305014,"id":"Q305014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$2A3481E2-1E0E-4423-AC58-42C1AFF9A232","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896869$958B1BCD-1234-4054-9F9A-17585AAB3C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896869$C61CBF0A-663F-45BC-BCB9-F7FC265AB54A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ea23561a0e441627818a7c69ffbc3c3d7a29894","datavalue":{"value":"7290981","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896869$860E4192-CAD1-466E-9846-CFFF7F414C66","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4d110bb717bc068263225c5ea7802cd0db4ab29","datavalue":{"value":"barrier coverage","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896869$22390EAD-797E-4731-B8F8-949B01150CA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"123052df6ab43fe38b66084e43785af4674b1f75","datavalue":{"value":"PTAS","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896869$3A54C61C-B904-446B-85E6-6C9E7A9827AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60b7a5cd7879e018a9143de96f9d289b742bf719","datavalue":{"value":"Weber problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896869$DABD9AF2-F87D-47E8-B0AB-CB0753EA1FAB","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":"Q5896869$4EE8041D-3F57-4FA6-9197-30592F70654F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d8ee1e3e219334a273bb492767ae75ce991658ac","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2020.101684","type":"string"},"datatype":"url"},"type":"statement","id":"Q5896869$84E3D552-D430-432B-B30F-69C13EA70DA9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee6674cf68a7ab84e9a5f553fe61e71d4175131a","datavalue":{"value":"W3040895870","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896869$318118E3-0EDC-484C-B225-F2C9D52F0CFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c3e30b49f4482ef88481594a358e1b5e2d548e5","datavalue":{"value":{"entity-type":"item","numeric-id":4943852,"id":"Q4943852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$673835B6-F70D-49DD-AE22-B6C5AC7619AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f10f3124af56047b3a7731cdb89fbe3bd75b1213","datavalue":{"value":{"entity-type":"item","numeric-id":1104865,"id":"Q1104865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$5ED3ADFD-4BE8-4A97-9ECD-515F3A8F535E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4bc196b9fa14206961976703e99ac6e9be9ec45","datavalue":{"value":{"entity-type":"item","numeric-id":1040594,"id":"Q1040594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$BE4E45D2-8F4D-4B67-A7B8-342FC6966258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a84473634926f2121fc0f124362d93c28b39516f","datavalue":{"value":{"entity-type":"item","numeric-id":1869747,"id":"Q1869747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$1527A00C-8F26-4EB2-9DFE-51C29CADD70D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f24eccd0cb74a0c3d1051c4d5883067f25d16e1f","datavalue":{"value":{"entity-type":"item","numeric-id":5915653,"id":"Q5915653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$A7B27EDB-46F1-4FE4-99BC-3C3CC12C3CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d828c111820d30fac6523c3ea57c0cd4737497aa","datavalue":{"value":{"entity-type":"item","numeric-id":2344757,"id":"Q2344757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$A23B2C30-4E5D-4464-B6C9-EE7A3A3FDC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f2278a7aa33d64e980055ae7ff42c01a16cdf98","datavalue":{"value":{"entity-type":"item","numeric-id":5415489,"id":"Q5415489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896869$48F7F7AF-B62C-436E-889F-6F5ED48CE8FF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9de570fb6b2ed1f7172eb98e23d39a10e4e9895","datavalue":{"value":"10.1016/J.COMGEO.2020.101684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896869$C48E0AD8-115F-4B02-A3E2-76343AF6D261","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57946fc7ea0d26deddfd5cb4f3fefad4ee67edf8","datavalue":{"value":{"entity-type":"item","numeric-id":5915653,"id":"Q5915653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5896869$03BC2812-D214-4B35-B941-90A44C449FB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fb847ae4ebc53ddf92ea156936d0316725c9e0d","datavalue":{"value":{"entity-type":"item","numeric-id":5056051,"id":"Q5056051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76c164ea7a225809091b61625690c987c9a1780a","datavalue":{"value":{"amount":"+0.8175833","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5896869$A89AC566-4673-4881-BA1A-0DF76269A506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8df6261f57d9618cfa9ad15d69c95d79c8022cda","datavalue":{"value":{"entity-type":"item","numeric-id":6051503,"id":"Q6051503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d3406ed23efdeecb90b0eb84e767ad803fe0400","datavalue":{"value":{"amount":"+0.8069539","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5896869$891DC187-8866-4985-8568-73FC6CC4C201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84e64c31714bd5e8a11bf104504f1f45257a174f","datavalue":{"value":{"entity-type":"item","numeric-id":721928,"id":"Q721928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c5b8a1f7c3c4e48c382df5d8a101cf85963848c","datavalue":{"value":{"amount":"+0.8067526","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5896869$9152A657-72AB-4DDF-9905-ABEC0694EF75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d1bd25d91336524520ae3903a5f182f3f17fd83","datavalue":{"value":{"entity-type":"item","numeric-id":5384125,"id":"Q5384125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6c5961a408dfd5296d0032a6bd290f7fb915da9","datavalue":{"value":{"amount":"+0.8031917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5896869$97BA992F-C4D7-4F64-B514-1621FD405BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8242e466f8630f2500cd69edb296dfd6c4334dd1","datavalue":{"value":{"entity-type":"item","numeric-id":3587364,"id":"Q3587364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd81fee03a4b73f43b88668f755050bc3fb2c9e8","datavalue":{"value":{"amount":"+0.79907584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5896869$20F8CF3B-6878-467C-9BB6-2753C22B7D9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5896869","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5896869"}}}}}