{"entities":{"Q680151":{"pageid":682000,"ns":120,"title":"Item:Q680151","lastrevid":63540024,"modified":"2026-04-11T13:51:13Z","type":"item","id":"Q680151","labels":{"en":{"language":"en","value":"A streaming algorithm for 2-center with outliers in high dimensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6828437"}},"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":"Q680151$8AA6D2A5-CC81-4839-9411-59567B057474","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"52776557506ba4a2311b5d6deed00621d357c90e","datavalue":{"value":{"text":"A streaming algorithm for 2-center with outliers in high dimensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q680151$97C1ECD5-13C3-4B3D-BE1B-2C3A40B84E8E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fe1eccbe64f905dbe699681c621eb188b23ca2d8","datavalue":{"value":"1395.68307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$68D8EA56-9238-47F6-BAD5-0A55FEFA7CA7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1965585f9ec7ce0f85c065a9502c3f3c1738dd72","datavalue":{"value":{"entity-type":"item","numeric-id":680150,"id":"Q680150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$3B4FE1D3-2AA9-4C9A-9BCB-1A830FC94905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5cc03dad24e1486aad32ba9f3135d06d96d856b3","datavalue":{"value":{"entity-type":"item","numeric-id":386425,"id":"Q386425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$B9455368-2F07-4DF4-873B-0E386C54D47C","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":"Q680151$884553B0-78AA-4D6B-A75B-EFDEDFF9BD9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95b522232ea59b3ec56dcb082cdf4e0641310e1b","datavalue":{"value":{"time":"+2018-01-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":"Q680151$82EF19C7-A58D-45DF-82B8-27B8FA0DF38A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"715440578bbb6bdb152982abf86d39556f5d0458","datavalue":{"value":"Let \\(P\\) be a finite collection of points in \\(d\\)-dimensional Euclidean space. In the \\textit{2-center problem,} one is to find two balls of minimal but equal radii that contain all of \\(P\\). In the outliers variant of the problem, one allows some points from \\(P\\) to lie outside of the two balls. Under the streaming input data assumption, where only a single pass over the set \\(P\\) is allowed, the authors present and establish the correctness of an approximation algorithm for solving the 2-center problem with outliers. Specifically, the algorithm produces two equal-sized balls that contain all but at most \\(z\\) points from \\(P\\) and with radius that is within a factor of \\(1.8+\\epsilon\\) of the optimal radius. It has a \\(O(d^3z^2+dz^4/\\epsilon)\\) space requirement, and an update time that is polynomial in \\(d\\), \\(z\\), \\(1/\\epsilon\\) (an explicit expression is not given).","type":"string"},"datatype":"string"},"type":"statement","id":"Q680151$831626B4-3916-4FDD-A1F2-CF80D3FA19F0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c9684a93e5f98988685744c9cbf253435c411cf8","datavalue":{"value":{"entity-type":"item","numeric-id":510384,"id":"Q510384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$94D95E43-B593-42DE-A66B-4BB56DA9F210","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$08271007-7FF6-4C69-83C9-B4BE23CEEC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$77844099-A2DB-4CE6-9A33-2574AD0D42AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$D4BDDCBE-09E4-467D-B285-36BADE1CCB6F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5b9822e878fd050d7bdf6170a2180fa36f084e9a","datavalue":{"value":"6828437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$2534AF04-8D14-455B-B11E-FC580A25D524","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"959781ae798fbb43610e2c8d59c2daa47530b98e","datavalue":{"value":"\\(k\\)-center","type":"string"},"datatype":"string"},"type":"statement","id":"Q680151$472FF4BA-E0CB-4912-B172-BA8FC8CE7EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acbc508f2c665ca2fee93d0072ae30fb4c955d74","datavalue":{"value":"outlier","type":"string"},"datatype":"string"},"type":"statement","id":"Q680151$9AC71D5D-2D7C-4CCC-8331-C04496260E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fef5728e91ecb312cacaec9284e7d0f97905a585","datavalue":{"value":"high dimensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q680151$AF364292-4337-4DA4-99E8-DD9605AA5BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01cc19e176fd227ee72c622e015022e35bea68e1","datavalue":{"value":"data stream","type":"string"},"datatype":"string"},"type":"statement","id":"Q680151$AE7A19D5-E8A4-44A7-8DF0-95CE5731881A","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":"Q680151$0F651095-610A-4D59-A6E7-5BEDE689CAA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f69fd21a17cb35068e6ffe98dfe09fd9d1102fe0","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2016.07.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q680151$72F640BE-0744-4A3D-B32C-F3C1F08CAB99","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"59de839abfbdc9e52cd78c461e019c274b85b2fd","datavalue":{"value":"W2431755278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$6EED1F23-FB30-44BE-987F-62CFDE5FD7E1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83b7c61dc8364552778306e31217c785ea0b731b","datavalue":{"value":{"entity-type":"item","numeric-id":3541075,"id":"Q3541075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$27E979A9-82CC-4E43-AD84-1183735C671C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d48c58e9c3eff363c18dacfefacb6555f4cf8f57","datavalue":{"value":{"entity-type":"item","numeric-id":5417724,"id":"Q5417724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$6CCDA52D-530E-4A8A-AFD1-428E470D4303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21b8d70255a6f5487234c19700da72ed1cfdc8f","datavalue":{"value":{"entity-type":"item","numeric-id":3602850,"id":"Q3602850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$E159A7D1-0456-472D-B771-82EAA34A1D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c4459de820e0cff760a1f9f177984f6abb2e007","datavalue":{"value":{"entity-type":"item","numeric-id":390131,"id":"Q390131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$73B57B87-823A-4F1C-99AF-91529332C533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9c69e308d415a20025d0555b7fa5cf7a78db2c","datavalue":{"value":{"entity-type":"item","numeric-id":1961384,"id":"Q1961384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$37388893-A6A4-4882-8582-0DCB3CE8D02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cff1aa1732aba5c939e1a2c6ca06316b6a55c4b","datavalue":{"value":{"entity-type":"item","numeric-id":2768359,"id":"Q2768359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$E9727292-8927-4F32-B541-EF578DF24AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f55924d33b5698c3869722c3ed515e72d5d3f5a4","datavalue":{"value":{"entity-type":"item","numeric-id":3837388,"id":"Q3837388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$653AB955-4624-4B04-8EBA-B03591EB55D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98c1c1fb7004bafa5be39b458d78700fcf53cd64","datavalue":{"value":{"entity-type":"item","numeric-id":5341481,"id":"Q5341481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$4A111F97-FF00-44A5-BD05-04215B088BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"307fb49f6fe2fb59c207608c4367a76916d437d2","datavalue":{"value":{"entity-type":"item","numeric-id":1157170,"id":"Q1157170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$BD8AFF98-E185-4C12-B5A3-CBDE15509FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ced92ffe6f24eb3f8f20cb086cdbf15a59a8a3d","datavalue":{"value":{"entity-type":"item","numeric-id":1059958,"id":"Q1059958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$D0598F02-5255-4A16-8C27-A9C27C2238A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f555cba2271b4974b67495d471d4df13dff2f86","datavalue":{"value":{"entity-type":"item","numeric-id":904105,"id":"Q904105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$E0946239-1854-446B-A635-EC7B2CBFE51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac24fff19626ea43de3272fdf0df7273f8fb8a67","datavalue":{"value":{"entity-type":"item","numeric-id":1906043,"id":"Q1906043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$FC0DFD61-58A2-48B2-88C7-B9ADF6DFA8E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c77248cd584c811161fe08d221734e1cb434f51","datavalue":{"value":{"entity-type":"item","numeric-id":3541794,"id":"Q3541794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$A00BE969-ED69-46F2-9F69-9ED8E8FE9DFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43fb7b3f2b608d181bbfa5e3554cc627374b55ac","datavalue":{"value":{"entity-type":"item","numeric-id":547286,"id":"Q547286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680151$51A5B55C-82B6-4497-805F-D2C45A09B6DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a0d2527356638eb12ff733573088e481a62b37d9","datavalue":{"value":"10.1016/J.COMGEO.2016.07.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680151$08EC413D-3D45-4765-9A25-4B35CBBA9AA0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77e19b751e4720b17f5a7949091d3cf17629b254","datavalue":{"value":{"entity-type":"item","numeric-id":2939917,"id":"Q2939917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c2c2d0b181f1324b319ae3cf673d45aabd4e4c2","datavalue":{"value":{"amount":"+0.8376291394233704","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":"Q680151$9E6F7392-AF1D-46BF-9D14-BF1A29E7D1CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5e828ab288ed023d0ddc36db4b74f308da86626","datavalue":{"value":{"entity-type":"item","numeric-id":4909522,"id":"Q4909522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fe9e46c1c005530d0cdd2bcfcd68cc229a6bf05","datavalue":{"value":{"amount":"+0.8305930495262146","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":"Q680151$56729617-0691-45AC-885F-9301BD7820EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95f2b8075039a571925395c7c3b4ee98e480bb4f","datavalue":{"value":{"entity-type":"item","numeric-id":3612586,"id":"Q3612586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13cda3ceed133a00747504460bbf81f2cb206e25","datavalue":{"value":{"amount":"+0.8299503326416016","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":"Q680151$009D8417-5F51-4D83-A2B5-69DEB06E024A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"001171554ddf08aaf74e7e4f10273c4e90c1d408","datavalue":{"value":{"entity-type":"item","numeric-id":904105,"id":"Q904105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7ee16572c5ac793e998995856c3f4b20f001c8f","datavalue":{"value":{"amount":"+0.8260704278945923","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":"Q680151$45573D01-F009-4FC2-A136-F2B605AD8153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d65053573dff2a2fa2776b865e9b2e130ba70bac","datavalue":{"value":{"entity-type":"item","numeric-id":5405046,"id":"Q5405046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d69dbf4e1f572de009026ddfac9992a1610956e","datavalue":{"value":{"amount":"+0.8199862837791443","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":"Q680151$2E27C38D-E5B9-4944-8E5E-2B94598ABE4C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A streaming algorithm for 2-center with outliers in high dimensions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_streaming_algorithm_for_2-center_with_outliers_in_high_dimensions"}}}}}