{"entities":{"Q1262124":{"pageid":1272874,"ns":120,"title":"Item:Q1262124","lastrevid":68323029,"modified":"2026-04-12T22:56:17Z","type":"item","id":"Q1262124","labels":{"en":{"language":"en","value":"The double selection problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4123292"}},"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":"Q1262124$88E58D9C-E799-4D99-919B-9314795E79AB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7ac507ca15f13b7ab2be9c4de8adf1fe7f11e4c8","datavalue":{"value":{"text":"The double selection problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1262124$352D8C39-96A8-44BD-A83E-8CB14DC4731E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f25a3f885a2356b7d5ea5b4bfc2bc5a7d4518a1b","datavalue":{"value":"0685.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262124$C4FFE35B-A893-4F71-A1B4-3099760C2209","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eb0c3a8945cb5ad007471a95117bb9d2a857f5c1","datavalue":{"value":"10.1016/0012-365X(88)90128-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262124$760D95B9-1B7A-49DA-BF2E-657129DF7D1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"289d49a761dfac02c62be4b7f68381ebc5e52ce3","datavalue":{"value":{"entity-type":"item","numeric-id":495333,"id":"Q495333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$AA1A482B-0C1E-4B60-8EB7-6F29874ED99C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$15C3A5BF-6BB3-4EAF-B42D-B5EA51E6F9A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1262124$F4206FF7-1353-4E50-8981-94D21808E393","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b2b60e699970246b5775fcdac4f932fb7de0946","datavalue":{"value":"One of the most intensively investigated problems in combinatorial search theory is the selection problem. One searches for the minimal number \\(V_ s(n)\\) of pairwise comparisons required for determining the s-th largest element among an unknown order of n linearly ordered elements. The present paper investigates the related problem of locating both the s-th and the t-th element. The resulting quantity is denoted \\(V_{t,s}(n).\\)    Two special cases of this problem are well known. The case \\(s=1\\), \\(t=2\\) asks for the largest element and the runner-up, and for this case a tight bound \\(V_{1,2}(n)=(n-2)+\\lceil \\log (n)\\rceil\\) has been given by Kislitsyn. The case of determining both the largest and the smallest element has been investigated by Ira Pohl: \\(V_{1,n}(n)=\\lceil 3n/2\\rceil -2.\\)    The author derives by a potential method two general lower bounds, one of which is suitable for small s-t and another which provides reasonable results when s-t is large. For the cases \\(t=s-1\\) and \\(t=s-2\\) matching upper bounds are provided. Also for the case \\(t=2\\), \\(s=n\\) a close upper bound is obtained.    It is shown that the required number of comparisons is always at least as large as for the known case \\(t=1\\), \\(s=2\\). A related problem, investigated by Varecza, is the determination of the required number of pairwise comparisons required for verifying that a given pair a, b indeed is the solution of the s,t selection problem. For this related problem bounds are provided as well. The author finishes with a conjecture due to Hastad stating that the selection of a pair of adjacent elements is asymptotically as difficult as selecting the first of these elements. If true this conjecture, in combination with the bounds in this paper, would prove a lower bound of 2n-o(n) for the median problem. The best lower bound for this problem so far, according to the author is 1.75n-o(n). It should be noted that for this problem an improved lower bound of \\(79n/43+O(1)\\) is listed in \\textit{G. H. Gonnet}'s Handbook of algorithms and data structures (Addision-Wesley 1984; Zbl 0665.68001). Previously an lower bound \\(11n/6+O(1)\\) had been claimed by C. K. Yap.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262124$A15BCD39-DD73-4E0C-B4E1-0841C3187CE1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262124$D90894E1-60C5-4549-900D-708844DD3269","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"792126eb2b29d24902eb5aaeeaa2ae7d514276d3","datavalue":{"value":"4123292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262124$14DB8115-B1E2-4E98-8854-840D9357D99D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126bc261b4ce15426bca501a6725c284417e2bf6","datavalue":{"value":"partial order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262124$B1198AC7-FEAB-455E-A9AF-B2CE7027A106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99c8173fae6010aa47d7fbfcf07c2f94dd931ef4","datavalue":{"value":"comparison algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262124$EC2CDB1B-06A5-4BC8-A6F5-1116022418C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d083787e5b9d94f3db595823f9cff1c8584e905","datavalue":{"value":"selection problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262124$E53B849A-BFC0-4E54-82A6-FDC15D20D765","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ca9cd2a9131e1d8839142cee57f1e863d7371382","datavalue":{"value":{"entity-type":"item","numeric-id":582045,"id":"Q582045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$4C416A23-9553-4E6E-8073-53500F12EE18","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":"Q1262124$AA79B581-CD46-4140-9ED0-6B9AE2B70867","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ffb77b61ca562ead99a5502fc35c5a47098aed0","datavalue":{"value":{"entity-type":"item","numeric-id":1151047,"id":"Q1151047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$30BF3CC4-BD4C-487C-BEDC-75B355628F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"967d94d15be5929b371046cf005071ce131361ab","datavalue":{"value":{"entity-type":"item","numeric-id":1171878,"id":"Q1171878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$130A82D0-04BB-4C0C-9CE1-66119CF12F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7cfb7bf7314db68e2fa5b66984e374763ca1181","datavalue":{"value":{"entity-type":"item","numeric-id":4181962,"id":"Q4181962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$CF440A43-E626-4E5E-8315-8D08EBB234EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"290a874e6b5defe246b06a0d481a3b05c781aa50","datavalue":{"value":{"entity-type":"item","numeric-id":5183260,"id":"Q5183260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$EEDEC39E-9644-42FF-B92F-591A0EFF53E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52207ca46ee1ffb3be331ab94c7e273c8da0922e","datavalue":{"value":{"entity-type":"item","numeric-id":5601827,"id":"Q5601827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$07311F55-F74C-4211-9D39-E524F67E93E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66aa54bfb7a43ef696f12a804d0d05acf1a4d555","datavalue":{"value":{"entity-type":"item","numeric-id":3706485,"id":"Q3706485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$959640A9-9F3A-4226-9039-8525BF652804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"640b2812406d6b3f12b417bf188690c1899ce32f","datavalue":{"value":{"entity-type":"item","numeric-id":5643583,"id":"Q5643583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$E052EBE2-1E90-4308-821B-DF2055E24338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"257001b5ea4ce59499d55ccb1ebeb946df7a89ba","datavalue":{"value":{"entity-type":"item","numeric-id":1229583,"id":"Q1229583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$33F5CBEB-B869-494B-84CC-10AFA52123BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"781ba80ab90889b58a3da38a55b8de103efd1f83","datavalue":{"value":{"entity-type":"item","numeric-id":3907568,"id":"Q3907568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$510ED452-30B3-4F5A-8135-8D34928B0091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a61c91a5af9d2f30d70f692da40f155dd1d353d","datavalue":{"value":{"entity-type":"item","numeric-id":3329473,"id":"Q3329473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$B634CC91-268E-478A-9D6D-F4AF0DAC365A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2549aa33dcd20f2165260e08b6e579f6d53f002","datavalue":{"value":{"entity-type":"item","numeric-id":3703300,"id":"Q3703300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262124$99F8E9E3-C458-4DE2-8DB7-F6A5CA737CCB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d744d36f6fbaf000235442356ecdad3818a70712","datavalue":{"value":{"entity-type":"item","numeric-id":3829069,"id":"Q3829069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"142e2f4973f5bbc9e1e5b3d1ca2004dc44adcc00","datavalue":{"value":{"amount":"+0.8453120589256287","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":"Q1262124$55E1ADDC-4939-41DF-A875-3034EE194579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d92c509cd5f7df27638207a9d01536cb6d157b28","datavalue":{"value":{"entity-type":"item","numeric-id":2719174,"id":"Q2719174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d45f55dac76b51f18c779455593afd3a00de128a","datavalue":{"value":{"amount":"+0.8388985395431519","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":"Q1262124$CA1C1960-454C-46CE-A95C-DC215464E31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8475f98eea5781c0f2b525c4209c8c25b5f32f78","datavalue":{"value":{"entity-type":"item","numeric-id":4886030,"id":"Q4886030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d45f55dac76b51f18c779455593afd3a00de128a","datavalue":{"value":{"amount":"+0.8388985395431519","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":"Q1262124$FE19D0CC-9119-42E0-9D95-0F9D88363D2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"216240988be4fa4bea4254445b7e70ac2fe86fd7","datavalue":{"value":{"entity-type":"item","numeric-id":2719173,"id":"Q2719173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b87ae798b98460cb2dc358c7dcc846043a17db47","datavalue":{"value":{"amount":"+0.8376457095146179","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":"Q1262124$F43B1F65-7DA6-4BAD-BE49-8D2B673FF22F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"894efda741b5b99aacb8fc88913e43ef9f304b19","datavalue":{"value":{"entity-type":"item","numeric-id":4633820,"id":"Q4633820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b87ae798b98460cb2dc358c7dcc846043a17db47","datavalue":{"value":{"amount":"+0.8376457095146179","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":"Q1262124$ACBCA458-2DA0-4C63-8306-40F4B77789FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The double selection problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_double_selection_problem"}}}}}