{"entities":{"Q917229":{"pageid":919077,"ns":120,"title":"Item:Q917229","lastrevid":65332473,"modified":"2026-04-12T01:51:41Z","type":"item","id":"Q917229","labels":{"en":{"language":"en","value":"Weighted median algorithms for \\(L_ 1\\) approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4155777"}},"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":"Q917229$529E56F6-6D99-4A35-AC5C-E6281FCABB04","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"845e8aff0b134d601c259bc3651a206946ed371a","datavalue":{"value":{"text":"Weighted median algorithms for \\(L_ 1\\) approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q917229$86FF5BFE-1F89-4B23-BF0D-C868C9B8C7D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"521ff257fafa5f5a5589f2e403b2c1ee7fcae1f9","datavalue":{"value":"0704.65044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$B7E49809-D76F-4BC1-918A-2775B78D6E8C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7ade29f439a5816a7198431392074ce3fad6e7b","datavalue":{"value":"10.1007/BF02017350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$8C8AAE2A-9264-490B-83E9-A9242A171EE0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18d8997fe31ac5897e00c2a51fe811b925c7b55b","datavalue":{"value":{"entity-type":"item","numeric-id":917228,"id":"Q917228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$CFCD4141-2F74-48A4-9540-EF3A116A1812","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$E0E6FF6C-2EE9-426D-B219-514741BE7092","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q917229$7FBD58E9-E6ED-4DE5-8B36-98E3E57410DC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0851200f74892a647bf6a2bac971d3e3c3daebd8","datavalue":{"value":"The weighted median problem consists of minimizing the function  \\[  f(x)=\\sum^{n}_{i=1}w_ i| x-x_ i|,\\quad x\\in {\\mathbb{R}},  \\]  where \\(x_ 1,...,x_ n\\) are given real numbers and \\(w_ 1,...,w_ n\\) are given positive real numbers (the so called weights).    For solving this problem three algorithms (a partial heapsort method, a linear-time method, and a partial quicksort method) are presented and compared with each other. All these methods are based on the (necessary and sufficient) optimality condition  \\[  \\sum_{x_ i\\geq \\hat x}w_ i- \\sum_{x_ i<\\hat x}w_ i\\geq 0\\text{ and } \\sum_{x_ i>\\hat x}w_ i-\\sum_{x_ i\\leq \\hat x}w_ i\\leq 0  \\]  for a solution \\(\\hat x\\in {\\mathbb{R}}\\) of the problem.    Computational experiments (on using a Fortran compiler on a VAX 11/780) are reported and show that the order of the three algorithms given above also reflects their performance in terms of CPU-times in different cases for unweighted problems (with \\(w_ i=1\\) for \\(i=1,...,n)\\). For weighted median problems modifications of the three algorithms are compared where the partial quicksort method turns out to be significantly faster than the other methods.    An application of some of the algorithms to the line search in solving the multidimensional linear \\(L_ 1\\) problem is also discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$02103F71-4461-440E-8EED-18FB50E14B33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$B59F2BB6-DB71-4371-A511-B363DD506B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$F489E40B-E7AB-4FEB-A9C9-DCFC8F870231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fb3a8bd6d20cd71ea48713e39f04a71a6d560116","datavalue":{"value":"41A45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$10590B0F-F387-43B0-956B-69108FF639DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ea8d7fd647e9503babc529061be6b6d7b00c9e13","datavalue":{"value":"65D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$D623FC89-886C-4CFD-9DB5-57B9AA7C94E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a54103a62b355dbff736fc1657c9d241bb3b2b82","datavalue":{"value":"4155777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$94D0B302-6B14-4D88-B43F-986549A10E47","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"930deaa087f0a66c722f56d1e6733baf6b4ad0d9","datavalue":{"value":"weighted median algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$1ABC80C5-228E-4D67-8861-89423B1FCEB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad0efbf983573bcaa6eee3d75da5cbbe63943995","datavalue":{"value":"\\(L_ 1\\) approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$A18E381B-1C46-4B54-A06F-463A4E1C5F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"888427a5641477bfc2190dce6707a99baf90120f","datavalue":{"value":"sorting methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$5FA34F3D-F5D4-4858-924A-B2D2BBE94D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0912464b9cbe26bea1c6c1a2b5619cd1388d2bd","datavalue":{"value":"partial heapsort method","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$BC50384F-39E7-4E5E-BCBF-C64BE028DFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adbff0a37766ce6de487c602fbb5f99fbb5dca65","datavalue":{"value":"linear-time method","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$25DF8E07-2CF7-46BA-B5D5-5C3281451C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea1bde28b27572163ae6c6fef75cf85538956d70","datavalue":{"value":"partial quicksort method","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$4EFED55C-49D5-4717-BB30-2601B0CCE12A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"248a08916b1214301675d648fdedebc30bc34521","datavalue":{"value":"Computational experiments","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$54B0F1B1-2488-48F6-B947-475E83656702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d29ab8b57f7ba662728a4122498bb0b711727713","datavalue":{"value":"line search","type":"string"},"datatype":"string"},"type":"statement","id":"Q917229$8646E5A2-E8BD-4B6F-A06B-89836EB103DD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1602a325d3d2fc4285dfc7653c52bde7eb00c007","datavalue":{"value":{"entity-type":"item","numeric-id":579218,"id":"Q579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$E5E2B3D1-65B1-4C1D-98C6-02C92746BBA5","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"9aadc3562b5d3cd99740f94e9d46e7f210998eaf","datavalue":{"value":{"entity-type":"item","numeric-id":33419,"id":"Q33419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$84258B7A-A1F1-4D52-909C-C5F813D54355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c40f8bcf9e737e0972f90fa9fce9b2e122f6fab0","datavalue":{"value":{"entity-type":"item","numeric-id":51976,"id":"Q51976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$D64C6A7F-645A-4358-B35F-6818D9EA5193","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":"Q917229$3A7E4935-8425-4275-B087-1C6529CDF105","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$21706A45-4926-4353-B9F7-82FEBAF5626D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f0e688b866fa0d0fb34601ae82f3743edd37f37","datavalue":{"value":{"entity-type":"item","numeric-id":5683621,"id":"Q5683621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$59318B67-5C42-4BB2-8674-0DDEE3969C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47f33783bb42a2cfd11f4a6c2131e34bab1ef08f","datavalue":{"value":{"entity-type":"item","numeric-id":4153546,"id":"Q4153546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$6EF7E505-8C4E-4EA0-B726-D0AEBE2ACE69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ff3d81ba94b595fc96b77ed62611cee5f5a6297","datavalue":{"value":{"entity-type":"item","numeric-id":3925063,"id":"Q3925063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$22E39C60-7B8B-4000-A3C2-F368E81E1E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$286F1B46-FAB9-4A35-A99F-1F99EABB4B88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41054d964c4a7c5d7469aabb01982a9e622f0b17","datavalue":{"value":{"entity-type":"item","numeric-id":3923523,"id":"Q3923523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$57FEB6B8-3FB4-42D0-A5D0-05DEDE9FFF66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13d97cd31123da2b55534df203665b73396f2ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4050138,"id":"Q4050138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$351EAAB9-BF97-4124-B4F8-A9CE9CCCCA2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd9885056b1855f557ad76325bd57251833c73a","datavalue":{"value":{"entity-type":"item","numeric-id":4154059,"id":"Q4154059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$4513554E-2BB7-4739-8909-36036B0EB20C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$77164135-E162-448F-B821-02ACF085DB0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"689a4200fac8995bc16e67741d0b5a1137150f4b","datavalue":{"value":{"entity-type":"item","numeric-id":3321365,"id":"Q3321365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$6188BFB2-4833-4343-A0A7-6BBBDF05A1B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f40c99e5bd7a072ae1051093a8d56c26a7d43f2","datavalue":{"value":{"entity-type":"item","numeric-id":1249045,"id":"Q1249045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917229$AF4C3C33-2786-41FE-8A83-E2AC4AB69D9D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5620c93f0e3b7e8ca03815de633c212dc6174d85","datavalue":{"value":"https://doi.org/10.1007/bf02017350","type":"string"},"datatype":"url"},"type":"statement","id":"Q917229$4B04D708-16DF-41CD-B165-402342E7A968","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f7ef0bba0a040378b01ef6880f37e445dde71b59","datavalue":{"value":"W1542365154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917229$07B293AE-CEBA-4E0A-A373-78FD1EC1D4A7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e06639809aa087ac2f2c6d256eff1a845cef83b","datavalue":{"value":{"entity-type":"item","numeric-id":3168545,"id":"Q3168545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8db75553e52f3d45b4ce39d5bc5ce55abd2e6343","datavalue":{"value":{"amount":"+0.8309846520423889","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":"Q917229$C4DE79DF-AD76-4FF3-824B-C209607F535F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02d26a17c4dc6429ca10e97ed548e8104f3f4823","datavalue":{"value":{"entity-type":"item","numeric-id":294747,"id":"Q294747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c4fc682a60c8ba260ba44b0b20d0f07bd53a9e5","datavalue":{"value":{"amount":"+0.7714707851409912","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":"Q917229$379945ED-447B-4CE3-AA1C-714B32EAC74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a7f6151fcf55e6fa31f8972795329102b81b0a8","datavalue":{"value":{"entity-type":"item","numeric-id":2367406,"id":"Q2367406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"911188bd9a97f9c2d304083bf6843fb1519a1e14","datavalue":{"value":{"amount":"+0.7692514657974243","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":"Q917229$A147B2B4-9A67-4832-A88B-2AC550324AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8ef026aaf05d1b7422d9673a37a05738f53e030","datavalue":{"value":{"entity-type":"item","numeric-id":2512736,"id":"Q2512736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6424728e9ea44a70b04224c880a8031b70489c5f","datavalue":{"value":{"amount":"+0.7607679963111877","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":"Q917229$CFF40D64-25A0-49C6-8276-6FA9D9E997D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd0363a3a565e040b4260e296b3380c53468f1ce","datavalue":{"value":{"entity-type":"item","numeric-id":5472498,"id":"Q5472498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a96f5c89102d067497bf0e73e97483f100d9dc70","datavalue":{"value":{"amount":"+0.7601115107536316","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":"Q917229$5574BF98-23D5-4DD8-9A54-5C3159A3DC5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Weighted median algorithms for \\(L 1\\) approximation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Weighted_median_algorithms_for_%5C(L_1%5C)_approximation"}}}}}