{"entities":{"Q1767886":{"pageid":1778628,"ns":120,"title":"Item:Q1767886","lastrevid":74150661,"modified":"2026-04-14T18:36:49Z","type":"item","id":"Q1767886","labels":{"en":{"language":"en","value":"An algorithm for discrete approximation by quasi-convex functions on \\(R^m\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2142421"}},"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":"Q1767886$0C4D6183-E33A-4FF6-BD98-60A65EA834E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2f64ebf76bb79c0a9619d6f3da992ce861055e5","datavalue":{"value":{"text":"An algorithm for discrete approximation by quasi-convex functions on \\(R^m\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1767886$82F73119-9DD2-4E27-92E3-40F55FBC7088","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5ad4bb5e73ded0892a7cbf226071e87954cc2b86","datavalue":{"value":"1077.65013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$71CC8448-5901-40C7-8F6D-C2726B1DF24E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bd47d06c0da02a3275cef5e1a053a13d04438c27","datavalue":{"value":{"time":"+2005-03-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1767886$21D3E8EF-DF47-4F6B-A56A-8B70E50DC175","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21f21b3b2ad85e91c4c60a1a4e166bb039682c8a","datavalue":{"value":"Let \\(T\\) be a convex subset of \\(R^m\\). A function \\(k'\\) on \\(T\\) is said to be quasi-convex if  \\[ {\\;k'(\\lambda s+(1-\\lambda t)\\leq \\max(k'(s),k'(t))} \\]  for all \\({s,t\\in T}\\) and all \\({\\lambda\\in [0,1]\\;}\\). Let \\(S\\) be a finite subset of \\(R^m\\), \\({card(S)=n}\\). A function \\(k\\) on \\(S\\) is said to be quasi-convex if there exists a quasi-convex function \\(k'\\) on the convex hull of \\(S\\) such that \\({k=k'}\\) on \\(S\\). Given a real function \\(f\\) on \\(S\\), the problem is to find a best quasi-convex approximation \\(g\\) to \\(f\\) in the uniform norm. Denote by \\(K_f\\) the set of all quasi-convex functions \\(k\\) on \\(S\\) such that \\({k\\leq f}\\) on \\(S\\). The function  \\[  \\hat f(s)=\\sup\\{k(s):\\;k\\in K_f\\}, \\;\\;s\\in S, \\]  is the greatest quasi-convex minorant of \\(f\\). The best quasi-convex approximation to \\(f\\) is obtained as \\({q=\\hat f+\\Delta}\\), where \\({\\Delta=(1/2)\\| f-\\hat f\\| }\\). An algorithm for computing this best approximation is developed and its complexity is analyzed. In the case \\({m=2}\\) the worst case complexity of the algorithm is \\({O(n(\\log n \\log r+r))}\\), where \\(r\\) is the cardinality of the set \\({\\{f(s):\\;s\\in S\\}}\\). Some observations that will speed up the algorithm in the average case are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767886$D1CB0CD3-A755-45D8-A0C6-E9C08165EC91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2afc8b14470e661c10725547661d94fa1583b792","datavalue":{"value":"65D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$9F650C40-4837-4353-A03E-C6EC59FB4AF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c062103713bbaad5cf8d3fcfa14d43e9ef183341","datavalue":{"value":"41A50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$E680BEFE-BD3F-4F94-A9F5-915BBC49C91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$6E30AA26-F54C-41F2-A6BD-1C8B66709449","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4260cf428a8a50c26fec0e66a9cac3764c0c9807","datavalue":{"value":"2142421","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$B3B5D2A2-4117-4D69-A1E6-2CF0DD6119DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e6a1b5210742695b93165a37eb637da77086e1d","datavalue":{"value":"discrete approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767886$457139C7-A788-40F1-9421-158E3531F6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3361247f8e9cbb068974ed1983be705ccbe4142","datavalue":{"value":"quasi-convex function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767886$D39D28BB-48B5-467F-910C-B705DE7BD040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d3ba1f6633d528ac942e9f81ac613dafaf9f6fe","datavalue":{"value":"best approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767886$C39905D4-3A8A-44A3-9616-4CFB569FF144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767886$0F31FA0C-8199-487B-9CF2-25462E0B3E07","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"28016a6519797105198db76e8484906c918f2d5a","datavalue":{"value":{"entity-type":"item","numeric-id":792059,"id":"Q792059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$C539607A-6F8F-4B32-B43A-9792275E0BA7","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":"Q1767886$213C1B9A-7A62-446A-9463-FB9B660DDECE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"50d6017c61c6ef10ea1e51637963c3be2e4a47bb","datavalue":{"value":"https://doi.org/10.1016/j.camwa.2004.06.023","type":"string"},"datatype":"url"},"type":"statement","id":"Q1767886$98C492DD-3C3B-4A2D-9616-6D055287BC60","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"515eb646166252655c54595948dd7c7013578d62","datavalue":{"value":"W2059728435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$E3A0D3BC-5D4A-4537-9B39-DFDF383E9031","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98ae31cb6d0ab549f2c2361eecff1638bb0dd12","datavalue":{"value":{"entity-type":"item","numeric-id":4777548,"id":"Q4777548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$4D6FAB7E-922D-43BE-A61D-0A97DE97B50A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"573132fa0a718bb4c404014b1da1d66629904a86","datavalue":{"value":{"entity-type":"item","numeric-id":4377583,"id":"Q4377583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$5047E65A-4E96-467C-B680-998A56C1E6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$F1235A19-E87A-4E4B-AD24-4EC11C15D41B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29f27c636d822aedfcb621168990c2025be43100","datavalue":{"value":{"entity-type":"item","numeric-id":4190154,"id":"Q4190154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$278DD8F2-7994-4878-AB5E-238326EE3DED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25fa1198b80017739f0fdb556bd9257106df7653","datavalue":{"value":{"entity-type":"item","numeric-id":4217293,"id":"Q4217293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$CEE1142F-DB18-4FF0-9FEE-9236F151ACCB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eedf059342b5045d887cfcf8aa652528836d7756","datavalue":{"value":"10.1016/J.CAMWA.2004.06.023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767886$EFAB144C-B288-4D99-B0B5-C61B3B4F7C8D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"293935db3834ff8b5d542ae1771b7c6cb66baa38","datavalue":{"value":{"entity-type":"item","numeric-id":85551,"id":"Q85551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767886$12C34E80-820C-499B-BF22-7586C2D8DAD4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"008d28269c345496237b0aab1dd3f4f55e9242b8","datavalue":{"value":{"entity-type":"item","numeric-id":1097626,"id":"Q1097626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e97cc140feabc75243e8c29c6ee2fe9591016fa","datavalue":{"value":{"amount":"+0.8863220810890198","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":"Q1767886$245C672E-B729-4C8B-A8AD-C74A98602755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2d2a36dc847965013e918d9e7cab90db5353f14","datavalue":{"value":{"entity-type":"item","numeric-id":2266345,"id":"Q2266345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f25b1315874f7e95b5ccdfc992a302990a2109e","datavalue":{"value":{"amount":"+0.8645920753479004","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":"Q1767886$5C5368D3-26BC-4A03-9ED1-96D6699D199F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"730126d1d66e9f49cfb6a2a5b8256cb39bcb39b1","datavalue":{"value":{"entity-type":"item","numeric-id":913166,"id":"Q913166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"725f9498dbfda55c129d7b420822df23d007f9af","datavalue":{"value":{"amount":"+0.8413882255554199","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":"Q1767886$A48246DA-3DA8-44F3-9382-44F497055FD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c226deda399c1caa993719a134bab099570b9f8","datavalue":{"value":{"entity-type":"item","numeric-id":1120770,"id":"Q1120770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3152236d3b69587d49c37f589bf808f18b2ed7c2","datavalue":{"value":{"amount":"+0.8409950733184814","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":"Q1767886$39B8A3E1-0B0A-4104-AD47-8E43D4E03DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3e0eaf1b08e4f16b06984cbdfd6c07d2d23bbea","datavalue":{"value":{"entity-type":"item","numeric-id":805957,"id":"Q805957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12bd10141b4b9b87a4c0ba6644fe789b435a0b6c","datavalue":{"value":{"amount":"+0.8334150314331055","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":"Q1767886$E01A1F5D-B38A-4924-B260-5766B94BC40D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for discrete approximation by quasi-convex functions on \\(R^m\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_discrete_approximation_by_quasi-convex_functions_on_%5C(R%5Em%5C)"}}}}}