{"entities":{"Q2331446":{"pageid":2342189,"ns":120,"title":"Item:Q2331446","lastrevid":56671530,"modified":"2026-03-18T15:41:28Z","type":"item","id":"Q2331446","labels":{"en":{"language":"en","value":"Approximation algorithms for the geometric firefighter and budget fence problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7123889"}},"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":"Q2331446$3FFD26E9-7A11-45C3-BE26-9602CF73BCF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9027c9ada553b69ade4271f7b52c5abce7cec25d","datavalue":{"value":{"text":"Approximation algorithms for the geometric firefighter and budget fence problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2331446$55D0ED73-4BC7-43E4-9915-BD4E8E4760FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0fcacc52b76056764d195fb219e54411d8886a28","datavalue":{"value":"1461.90051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$9906F237-E17D-41F6-A5C2-880FF77205B6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0dc835d004d9da5bffbf23ad19f48702adc4590","datavalue":{"value":{"entity-type":"item","numeric-id":582112,"id":"Q582112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$FF2F3936-F9B4-448F-9805-18C34F58E438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dfebb11dde3a8ec3e20741cb39008a3351335c","datavalue":{"value":{"entity-type":"item","numeric-id":293198,"id":"Q293198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$06FC9989-C453-4412-A3CA-6AF6940C4295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a1693234cb2b94788908b8e8a90f524543aea5b","datavalue":{"value":{"entity-type":"item","numeric-id":166235,"id":"Q166235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$D618FD1E-C96C-4A16-A2E1-799FCD2AFB8B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$3C20B287-7FB2-427F-B2B1-33D52C128B71","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"362960159b173a98e6b7060e1eb441bfdc739e81","datavalue":{"value":{"time":"+2019-10-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2331446$7D74A0EB-549B-44C8-9423-9DAAF1FC48F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4945ce1f016219149bd891ca08369297a8206a8f","datavalue":{"value":"Summary: Let \\(R\\) denote a connected region inside a simple polygon, \\(P\\). By building barriers (typically straight-line segments) in \\(P \\backslash R\\), we want to separate from \\(R\\) part(s) of \\(P\\) of maximum area. All edges of the boundary of \\(P\\) are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the \\textit{budget fence} version the region \\(R\\) is static, and there is an upper bound on the total length of barriers we may build. In the basic \\textit{geometric firefighter} version we assume that \\(R\\) represents a fire that is spreading over \\(P\\) at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set \\(B\\) that satisfies certain conditions. Even for simple cases (e.g., \\(P\\) is a convex polygon and \\(B\\) the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient \\(\\approx 11.65\\) approximation algorithm for the firefighter problem, where the set \\(B\\) of allowed barriers is any set of straight-line segments with all endpoints on the boundary of \\(P\\) and pairwise disjoint interiors. Since this algorithm solves a much more general problem -- a hybrid of scheduling and maximum coverage -- it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$4BF8B814-4541-4335-B217-B8A1E45617F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$DFD3B93E-D15A-4DDC-B4C9-3340288CBAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$83A3692E-2F3D-46BC-BFF6-D351DB25F132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$DFE1FFFA-AFFE-44AE-B844-BB99F32FE694","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6060e3766e7fc8709ed67dfe8e76778e11f766c6","datavalue":{"value":"7123889","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$42017830-9079-4A49-A865-E67FA8A8F62C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c619140a3078a766185364ee8a0702352fc4f41","datavalue":{"value":"budget fence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$EAB38961-020B-4245-A4F1-092D5CCEEE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbee060d2328ce2f7ad402b805b6071181be3167","datavalue":{"value":"firefighter problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$51E0ED14-9E1F-4C0C-A4C3-CF64D912D07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"123052df6ab43fe38b66084e43785af4674b1f75","datavalue":{"value":"PTAS","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$2051F68E-89D9-493B-9688-8EDEFC740CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$6488F2BB-B7F4-4C3E-AABE-A6C16B48AC57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"985d6383219d2a224506d6f09330b5560ef81c74","datavalue":{"value":"set cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$1561B40C-3028-4D9C-9340-8CB01FC062A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331446$FFCCE4A0-93A4-424F-9252-8F096E722ECF","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":"Q2331446$94941FE9-A98E-45F8-B9FF-F6406766B862","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52a00424e826c4edf0e9cfa7ae8f86e657dff409","datavalue":{"value":"https://doi.org/10.3390/a11040045","type":"string"},"datatype":"url"},"type":"statement","id":"Q2331446$7D8B9CEB-4B77-4DDC-8118-47807CCF5D7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7cb4ec8dadd6d6a68dd2eefcca1766bd4f25d1f6","datavalue":{"value":"W2797667638","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$F786D162-96BD-42CA-9B0B-091B28D2A73E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"94999b0826795998b6a9b4f597e8cdc9b04ae0bf","datavalue":{"value":{"entity-type":"item","numeric-id":2428668,"id":"Q2428668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$3CBF8155-452D-405F-AB36-13ED36666466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0dc8e8439d50d3fae778e184cdcf03995f2d236","datavalue":{"value":{"entity-type":"item","numeric-id":3596724,"id":"Q3596724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$9852149C-0405-4E43-9E1C-B5F1312D9CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c028844c09fc58ee4ae2ae9e9ef7a8fd66f0aee","datavalue":{"value":{"entity-type":"item","numeric-id":2370449,"id":"Q2370449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$935CA6FD-AC97-4BCF-BD0F-99189C09A8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a53ca109b5b68eb839785957a7f6c16bf7a5c68","datavalue":{"value":{"entity-type":"item","numeric-id":2841981,"id":"Q2841981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$D9699090-DE02-4FEE-B882-B02DD27F1CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89baaa7e4630b6268a9ca768c165384c9c08d2db","datavalue":{"value":{"entity-type":"item","numeric-id":3614015,"id":"Q3614015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$BE665FAA-4080-439B-9E3E-F85D097CDA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc9b50a8a10d88a40e78369937bbd6171616327","datavalue":{"value":{"entity-type":"item","numeric-id":5405045,"id":"Q5405045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$98930B1D-4F23-4AB9-B732-69517EA80263","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":"Q2331446$72943616-A758-4F21-9534-5987FE4F3081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5be09e8fffd862840e53d3904e5f6442e087dc7","datavalue":{"value":{"entity-type":"item","numeric-id":5252258,"id":"Q5252258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$933A137F-E46C-4DD9-9A6B-A4D5401EABEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b58031c6af924091b563c813c2578873fc8da1f","datavalue":{"value":{"entity-type":"item","numeric-id":1606925,"id":"Q1606925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$3D448677-F965-4A41-905C-B961F62DACC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"036cccd5079e104012a2c0be22cb2d9ca33712a1","datavalue":{"value":{"entity-type":"item","numeric-id":963466,"id":"Q963466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$37DB0065-59A1-4CEF-970E-D75EE2EE303E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e8eba5c3572d40a9e5ddf34aa50cd3b9614ac66","datavalue":{"value":{"entity-type":"item","numeric-id":5417729,"id":"Q5417729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$FB45A0EF-1E00-4B18-BE8A-FA980993C018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dde84fc0ba4001786831488784599f6fa6efcac","datavalue":{"value":{"entity-type":"item","numeric-id":5173251,"id":"Q5173251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$9DC47957-DBBA-47B9-93D6-966500252069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f335c017a877c2ba72251d5ff9766b64d4cb993","datavalue":{"value":{"entity-type":"item","numeric-id":5475880,"id":"Q5475880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$2C5D1625-C56F-40A6-8AED-793A322E7FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59218acad36a0a9321046a14c9a342490f398ca9","datavalue":{"value":{"entity-type":"item","numeric-id":5419149,"id":"Q5419149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$7816D87D-44E5-4C41-91CB-B2D617728AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f04519c1443fdb5c79767afb9feff136d843da06","datavalue":{"value":{"entity-type":"item","numeric-id":5384460,"id":"Q5384460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$BCC62E10-CCFC-4A96-9895-8BBA4B0CA4DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e15421471087bd90a0d7893e0b8486659938a2e4","datavalue":{"value":{"entity-type":"item","numeric-id":1652708,"id":"Q1652708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$B86AC604-69F7-4C4B-A156-C8BC80D83C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"465875cbe65092be18e4b4910ce88265f5a56960","datavalue":{"value":{"entity-type":"item","numeric-id":5174498,"id":"Q5174498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$82F4E0DC-722A-45B4-8722-11B401D441C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$12AD48AA-5E29-453F-B41E-B3E6C128CC8B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ef07c621386797cf598fc72d5fd9d6169ff6ad5f","datavalue":{"value":"Q129998273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$8DEA6B2F-40D3-417E-9595-F35378D4EFFD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"29dd539ff1a8f3e6dcd4c1caf1d06686c9f3b963","datavalue":{"value":"10.3390/A11040045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331446$DC93811B-AF5F-48FD-B2EE-65A3AEE05316","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"155b0d541e52fcefab8445a1292dceb1b322a33d","datavalue":{"value":{"entity-type":"item","numeric-id":5405045,"id":"Q5405045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cff81e79adbce2291bccb0301cf6179fd51525a4","datavalue":{"value":{"amount":"+0.9920764565467834","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":"Q2331446$FE1B8D47-5590-4CF1-9EA9-F978DC16B58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d5951c687859efa4ecdd81580db470c3f86b48","datavalue":{"value":{"entity-type":"item","numeric-id":1652708,"id":"Q1652708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9336c643a81db06a9a04282c8c766992aaae8345","datavalue":{"value":{"amount":"+0.7975274920463562","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":"Q2331446$2972042E-4949-4E1A-B377-8D17A8BD55DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe3373adabd8a05dbf94882d2038d251c75bcd9c","datavalue":{"value":{"entity-type":"item","numeric-id":5919320,"id":"Q5919320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72534cb5003be483d63ff7f51bee4f68fd9cdc79","datavalue":{"value":{"amount":"+0.7625021934509277","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":"Q2331446$7D9A68BE-C08E-4773-B560-843A483A323A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cc5cbfcffc3079bd7ea7683401b0cf04fdad18c","datavalue":{"value":{"entity-type":"item","numeric-id":5918101,"id":"Q5918101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6c374f44467f453b3c80a10398fc9f5acc5d133","datavalue":{"value":{"amount":"+0.7624159455299377","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":"Q2331446$E1211E4A-C28A-4E4B-9AF5-D2E00B670633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"577438e0eebfd38fca7d76c7095757b6045c68c3","datavalue":{"value":{"entity-type":"item","numeric-id":517796,"id":"Q517796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48d5c06bf7fde73abc7e0610d71900736c330e5e","datavalue":{"value":{"amount":"+0.7269357442855835","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":"Q2331446$72BA1F00-0044-4109-853C-080086794D6A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331446$988F200A-F98C-47BC-8623-35C09E0AF62F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2331446","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2331446"}}}}}