{"entities":{"Q1059958":{"pageid":1061806,"ns":120,"title":"Item:Q1059958","lastrevid":42845539,"modified":"2025-07-15T08:28:45Z","type":"item","id":"Q1059958","labels":{"en":{"language":"en","value":"Clustering to minimize the maximum intercluster distance"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3905667"}},"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":"Q1059958$FDCF834B-887C-499B-8008-C89C3F2D902E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"76716873c1419c31d4ab37322089b7cb2cd5ec43","datavalue":{"value":{"text":"Clustering to minimize the maximum intercluster distance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1059958$E9EB2C08-9F17-45B4-9473-28D3E755D5BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6e5143f7b25a2079578874ea181a85ef34717e2","datavalue":{"value":"0567.62048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$919649D8-315B-41B7-BD90-C59077D0287D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f71b73238d13d11205d9b97a61fc967751d4d8fd","datavalue":{"value":"10.1016/0304-3975(85)90224-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$A9D7588D-7AD6-4847-B5B0-D79793823AE5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc11152e79285b1105c94eee7fb922884a1cabd0","datavalue":{"value":{"entity-type":"item","numeric-id":293372,"id":"Q293372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$3E4E9139-62CA-4663-A877-31D9C52BC89A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$967755A3-E9F1-4116-9F25-82A554738F55","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1059958$73548D98-80CA-4617-A3A9-23DA158DF89F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4714bc205434e96d0c3a7d713ee477b97a80249","datavalue":{"value":"The problem of clustering a set of points so as to minimize the maximum intercluster distance is studied. An O(kn) approximation algorithm, where n is the number of points and k is the number of clusters, that guarantees solutions with an objective function value within two times the optimal solution value is presented. This approximation algorithm succeeds as long as the set of points satisfies the triangular inequality. We also show that our approximation algorithm is best possible, with respect to the approximation bound, if \\(P\\neq NP\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059958$C5FB2C65-9B91-48EC-8E16-DB5D86777CCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"48a59f52dcfcc38cd6697e0ef07319031311895b","datavalue":{"value":"62H30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$635E506E-5F8E-4560-B603-AACB64E6F3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$D6BA57D2-D0D3-4366-8F31-68B1B323A99F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b770d17a682e291506d9bcdcd9bfaf6046fe9563","datavalue":{"value":"3905667","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$8A44A79E-96F2-458D-8BBA-9654482865F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059958$C6B1D9F0-D8E2-47D5-BC66-1D89D71EA6E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd434e02b383cb93c3f98000f4a27a56dc9c6329","datavalue":{"value":"minimizing maximum intercluster distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059958$4A106CC2-C06D-4C73-8E6C-CF8DD9FCF7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9c4e650abc856b5f51d0b5123c5930fad01c53f","datavalue":{"value":"clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059958$1F81ACA5-3216-4AE0-B594-AA554AD4C681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059958$DA8C77DA-E0E8-465B-8678-926AD96D028B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f63460f8f31a42fab0d84a022027bf62e5c28c6","datavalue":{"value":"triangular inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059958$DCF1D4AD-5AAA-478D-9608-388FB5A132FF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"69cac6600df18c31a863cbd094224652d96c96fe","datavalue":{"value":"Q57568243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$3DACCB6C-B0C4-4F5A-91CC-C276A17E8092","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":"Q1059958$4A3EEB85-2A89-4CE9-9D01-CB37632637B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"48fd9af992ca5d588367e759821b7a57c43ae606","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90224-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1059958$66EA629F-94D6-4979-9EAA-67ED35A8859C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"80c3f5e809228c6e6bdf6fa33a406916ecaed184","datavalue":{"value":"W1973264045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059958$46AE30E3-F216-489C-8426-0CEBC6770E39","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"25faf2ffd2491bbfea243339b6721fe2e8e085bd","datavalue":{"value":{"entity-type":"item","numeric-id":5606288,"id":"Q5606288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$D5104E83-53B4-4124-91C5-EB935B241527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7af31fe071bf115bcd6070b9ea85c8936178cea","datavalue":{"value":{"entity-type":"item","numeric-id":5607645,"id":"Q5607645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$380D538A-A5E3-489E-95F0-F9323C393E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5296476e75679281d492c1b8cd5c9a41fcc1c21c","datavalue":{"value":{"entity-type":"item","numeric-id":5666148,"id":"Q5666148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$DC63F006-C878-4957-9552-951EE95FAC0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad7d325c3b0579152fec919cec7efa5585149f5a","datavalue":{"value":{"entity-type":"item","numeric-id":4181272,"id":"Q4181272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$F76C1953-2EFD-4D2A-AF82-EF543BBF7EB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7efb628eb41ed88361e43885e5d0aad567b83e9","datavalue":{"value":{"entity-type":"item","numeric-id":4403756,"id":"Q4403756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$CD60471C-C394-4947-85AF-8C7AF14E49B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e68a5e99a1a994740ea36df80f54f867241940","datavalue":{"value":{"entity-type":"item","numeric-id":5630496,"id":"Q5630496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$5DB9E085-2B71-4676-89A2-0466D27D493F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff3b7a2bfc235081ef2e7d03f8b83bc5e90262f3","datavalue":{"value":{"entity-type":"item","numeric-id":3252986,"id":"Q3252986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$F1F4FD2A-DFE8-4EC6-9EB0-A4113C79ED4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f687f896deb281a9a4515b3c324dabcea223218e","datavalue":{"value":{"entity-type":"item","numeric-id":3944005,"id":"Q3944005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$E811F118-AECE-44D1-8689-DF2F86B096AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc4f0630ec86e5a0d3e96a9ce7ec4c2915d07620","datavalue":{"value":{"entity-type":"item","numeric-id":4083458,"id":"Q4083458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$F59ED277-BF21-4D78-8431-872AE5EB7802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c52b21e2b050930655d553363cf317d38372f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3885184,"id":"Q3885184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$5D090AF2-299A-4A37-8BB3-AC82E97E029D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b99a18a7ff79e2bb23ee77c914bf24321c7d57c","datavalue":{"value":{"entity-type":"item","numeric-id":4749027,"id":"Q4749027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$3E98FB7D-5B98-41EB-A63C-6766FCF10670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$1B384383-0A3B-45CF-AE06-E495331D3AD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a18c7a1953676c337af8ec1952ee7433b0003479","datavalue":{"value":{"entity-type":"item","numeric-id":2557577,"id":"Q2557577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$68846405-B538-427E-8C90-4EA9CEBFD58F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf376f2946131481bf0c634e0ff1ff4924c8e63","datavalue":{"value":{"entity-type":"item","numeric-id":4119042,"id":"Q4119042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$B9B36116-2DFE-4984-A0DB-5D7BCFF2A7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a001774ef2aa6c19979875913d62e2af6b2814e1","datavalue":{"value":{"entity-type":"item","numeric-id":4138196,"id":"Q4138196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$B7AE0D3F-8B04-46A6-9E66-5865BA514F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a37d103b0980efe9ebda96b99dee36dba132e5b","datavalue":{"value":{"entity-type":"item","numeric-id":4176809,"id":"Q4176809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059958$FCCB30DC-AB06-4F41-B975-F6A316E43221","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bba1d1aa0800e9100b48b2b4205647f2b2f84d5","datavalue":{"value":{"entity-type":"item","numeric-id":5175947,"id":"Q5175947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74169f58246b9f6805a4929335cacb6f9b833979","datavalue":{"value":{"amount":"+0.9334294","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":"Q1059958$267E4724-40E7-40BD-9BC6-69A6439F7919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a30b83204d286b68202a55c5508ab20c3ba9ec0","datavalue":{"value":{"entity-type":"item","numeric-id":1887718,"id":"Q1887718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74169f58246b9f6805a4929335cacb6f9b833979","datavalue":{"value":{"amount":"+0.9334294","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":"Q1059958$F80A6BFF-A9D5-4A9C-BDEC-8841C98F544B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15db4e67e605be3ff35603f377f00a70e19a2608","datavalue":{"value":{"entity-type":"item","numeric-id":5317732,"id":"Q5317732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e5b65118daa9c5e7dce75fdb68bdd7e35bbbb32","datavalue":{"value":{"amount":"+0.8993897","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":"Q1059958$7AE7C2E5-3C9A-4064-8EEE-50A39BF45C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a19376fe5fd4ddf86be6169c0b2a68d674abc60","datavalue":{"value":{"entity-type":"item","numeric-id":581969,"id":"Q581969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8596e8b0ac40aa3777f90eef96e377505dfa6edc","datavalue":{"value":{"amount":"+0.8986045","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":"Q1059958$F66CE160-6CC0-40A9-8AED-A697DBD6EF5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43f791002847b8eb85ea8ed0f6cde0b1ec41510d","datavalue":{"value":{"entity-type":"item","numeric-id":5475856,"id":"Q5475856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce7ba2f00ea11f08bf5fa9ca8590c5426fb07f5c","datavalue":{"value":{"amount":"+0.8908494","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":"Q1059958$EBC9DC64-9E9E-423B-8115-7DD5FE44E04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7b6151247427a10c0fe9380b1a142a1e6b5b6e6","datavalue":{"value":{"entity-type":"item","numeric-id":2884573,"id":"Q2884573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1acad93ec59f1398a0200d5dc0ac647c2a3d13a5","datavalue":{"value":{"amount":"+0.8869457","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":"Q1059958$11E49230-3F99-428B-B843-FAE7FAE07FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f27402ea8514802c91e7898aa8c43e690245ec5","datavalue":{"value":{"entity-type":"item","numeric-id":1321669,"id":"Q1321669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c1bf2a63b28a3cd4bf05074ca8f88ff0e8efe58","datavalue":{"value":{"amount":"+0.8859019","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":"Q1059958$E0758536-A9E8-4754-BCB3-2973A86E5DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"492534d976908f365f0ace36ccf6634346fb14e7","datavalue":{"value":{"entity-type":"item","numeric-id":3005537,"id":"Q3005537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"120c58ef1d71bdd0ac33d4220aaac32bf01fbc30","datavalue":{"value":{"amount":"+0.8837349","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":"Q1059958$6C280B18-4214-4B96-AAEF-28D6480AE289","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1059958","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1059958"}}}}}