{"entities":{"Q1879248":{"pageid":1889990,"ns":120,"title":"Item:Q1879248","lastrevid":69180234,"modified":"2026-04-13T05:18:24Z","type":"item","id":"Q1879248","labels":{"en":{"language":"en","value":"Maximum dispersion and geometric maximum weight cliques"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2101909"}},"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":"Q1879248$3C289FAD-E198-4B2F-AE00-C84E07C908CE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2330db104479980b46b3e537d01c244118f02d32","datavalue":{"value":{"text":"Maximum dispersion and geometric maximum weight cliques","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1879248$8C7D84F7-39E5-4BE6-9FE8-7D74183EE05C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bc18837fa056975d99ed3016c86f65f0a659ca4d","datavalue":{"value":"1095.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$73F88E15-B3DB-4CAF-A71F-8395FEF6E530","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54d0fb42f157ab06e320b817ff28d77d672f4b10","datavalue":{"value":{"entity-type":"item","numeric-id":169289,"id":"Q169289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1879248$F0F52B8E-157C-45D4-BC6D-2A9D9382A4DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f577cdcdf1cf34b7984ed2233c4ea5de107f795b","datavalue":{"value":{"entity-type":"item","numeric-id":1379022,"id":"Q1379022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1879248$21A23F05-8969-41F1-A75F-03A92BEAB9E8","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":"Q1879248$E07A83FF-3864-4B43-B216-376599B4284B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7bd962bada8b0dc37e98aacdd29c36343a02c75","datavalue":{"value":{"time":"+2004-09-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1879248$BBB71FBC-647C-417B-91A6-869E55AA8B0E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"29cd3a545d0a3d547267fd2d7cfdadf16884c005","datavalue":{"value":"https://depositonce.tu-berlin.de/handle/11303/15964","type":"string"},"datatype":"url"},"type":"statement","id":"Q1879248$E627ECFD-5DCA-4D39-AAB7-E82A8817BA1D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5c47cc8db943f8316f3829ceffb85a0160dd10b","datavalue":{"value":"We consider a facility location problem, where the objective is to ``disperser'' number of facilities, i.e., select a given number \\(k\\) of locations from a discrete set of \\(n\\) candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in \\(d\\)-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where \\(k\\) is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where \\(k\\) is part of the input, we present a polynomial-time approximation scheme.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1879248$0AEF8E96-C4BF-4CD3-B681-4DAA2D3B3847","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$76BDF369-4A27-49DD-9E89-57FB1B152A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$E768E325-E070-4B3F-87F8-7F5A6E0CD6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$017021EE-59EC-490B-8952-36B81D9AA655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$915DE96F-7A97-44D1-B910-6D81150FB073","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"028ad718b6e69c9f7ad7b8c8fb228b66d62ba23d","datavalue":{"value":"2101909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$77385966-868F-473B-8678-83D37C1D8E09","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"600c1e6cd816b63470df7d348a4275d1b81cf52a","datavalue":{"value":"polynomial-time approximation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q1879248$0797A1C8-2811-4261-AA01-AC5B908B8439","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":"Q1879248$93C7EC89-3EB8-4F72-8D81-18888B4FB571","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0f7ef68858c8d0a1867dc86a76da3429aecd38c3","datavalue":{"value":"W2745300566","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$A411BB3D-CA07-4241-A244-74B91D47D6F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d264533ecf8331ed047e405921cd26ac6404d812","datavalue":{"value":"10.1007/S00453-003-1074-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1879248$C5352C0F-548A-4620-8178-2E1D06614151","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"991dc821f9f2822fe23217b31e16a1b7e9a23ac5","datavalue":{"value":{"entity-type":"item","numeric-id":2753733,"id":"Q2753733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc46660a5f61a39fe23b79fcf9ec8497afbe488","datavalue":{"value":{"amount":"+0.99999976","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":"Q1879248$D6397EEB-6B9B-42E0-A72E-F83AA5F36230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61454f22e52c49cee86d505dcd851d53cacf325","datavalue":{"value":{"entity-type":"item","numeric-id":5929139,"id":"Q5929139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25128f9f0428c7f83a83bb67483900063c45df41","datavalue":{"value":{"amount":"+0.9025243","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":"Q1879248$13CF6F6C-245F-4683-AE85-CAF82CC4846C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dddee553deaa56fde7f5a9739c543ab3b88989a","datavalue":{"value":{"entity-type":"item","numeric-id":3762347,"id":"Q3762347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24c4043535ade1443b8d5a10cc962252d2799d95","datavalue":{"value":{"amount":"+0.90093243","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":"Q1879248$DD8896D1-ACE6-4B9E-8D0B-752623C9E1D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b139f24edfe78342cfa7c780cd74db08f13219a","datavalue":{"value":{"entity-type":"item","numeric-id":1652358,"id":"Q1652358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96bad274b8488a7c03f9cf6454c8e4a9891fa324","datavalue":{"value":{"amount":"+0.8990449","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":"Q1879248$5272CBEA-514A-4D9D-8D40-51A2665AAB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd89fc6f7158ee0a51a5639c239153f0b1f30074","datavalue":{"value":{"entity-type":"item","numeric-id":1940437,"id":"Q1940437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70ffd2fb1435309c945f18f1e2bf0f4a6b12697d","datavalue":{"value":{"amount":"+0.8884975","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":"Q1879248$FA989D91-ECD3-4A8A-8BD6-B08E6BE6FC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3e6361c63293c96b4cf0245d928d7a84d06db4a","datavalue":{"value":{"entity-type":"item","numeric-id":4338575,"id":"Q4338575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c9e68d40802ec14453f1c4aa415c2167e1d23df","datavalue":{"value":{"amount":"+0.8859892","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":"Q1879248$A3A0A24D-0B78-4E2B-A073-6C7F1BD0D50A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e5cd9cf03881f15822973627f4f81a55e60f0ff","datavalue":{"value":{"entity-type":"item","numeric-id":1061136,"id":"Q1061136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7e24e8db62417ce5578dbf3c8dc913671c9481f","datavalue":{"value":{"amount":"+0.88179994","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":"Q1879248$6577393C-3621-46BF-9E9D-26F0F79E6F94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0779c28bd0f095679ef5da1cf78c916866661dd6","datavalue":{"value":{"entity-type":"item","numeric-id":1754725,"id":"Q1754725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d76189ba801e3caa933f980ed0137b9e87815cca","datavalue":{"value":{"amount":"+0.87896156","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":"Q1879248$7959D954-0636-43EE-981C-5EFBBED474C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"493f0aae1a49d4542fd0842c6737e3cc26da0fb9","datavalue":{"value":{"entity-type":"item","numeric-id":2655650,"id":"Q2655650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb212c26293f45fccd65bb18161b81fe4ce92c93","datavalue":{"value":{"amount":"+0.8784817","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":"Q1879248$1D1DEE98-395D-4390-99DC-88EF0BC47A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62993ba93eba4e27a7ec9275a404c0052f931841","datavalue":{"value":{"entity-type":"item","numeric-id":4817244,"id":"Q4817244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b1888cd1872aadd2cb367aeb4b2847ac8e92423","datavalue":{"value":{"amount":"+0.87827414","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":"Q1879248$848270F4-99B2-40C6-A5A1-EDE50EDD6D14","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum dispersion and geometric maximum weight cliques","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_dispersion_and_geometric_maximum_weight_cliques"}}}}}