{"entities":{"Q1375702":{"pageid":1386442,"ns":120,"title":"Item:Q1375702","lastrevid":71009451,"modified":"2026-04-13T18:52:53Z","type":"item","id":"Q1375702","labels":{"en":{"language":"en","value":"Worst case asymptotics for some classical optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1102610"}},"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":"Q1375702$4D38CC01-73E7-4B0C-B50A-E126C180EFAB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9249dcafbcba2d8c15a890af155c8464ab2e24dc","datavalue":{"value":{"text":"Worst case asymptotics for some classical optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1375702$4BE9957B-AA42-4B81-915F-A205DB6A29A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"43c433bf7e8ecc5c42a798241ee3dcc0d351711c","datavalue":{"value":"0881.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$4E98A1F4-F74B-4112-B967-C58F4C1B37B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0693552b3bf77fb8b8e433ae8a98e43ab1de02b2","datavalue":{"value":"10.1007/BF01271275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$22D255CE-A2FE-48CA-A60A-5C1B49A908AE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$FA95234C-C54E-4048-8AC5-F8AE2E498331","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b866ee3cb60433d92ae5f464f67832ea98456d1","datavalue":{"value":{"time":"+1998-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1375702$11700EF2-E5AC-4782-BA51-428FEB08D50F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"badffeeebb7cf88acf6a7fe00c3eabe18957097d","datavalue":{"value":"The author considers methods for obtaining the worst case asymptotics of some classical problems in combinatorial optimization and operations research. The attention is focussed on the following processes: 1. Minimal spinning trees (MST). \\( M(x_{1},x_{2},\\dots,x_{n}):=\\min_{T} \\sum_{e \\in T } |e |, \\) where the minimum is over all connected graphs \\(T\\) with vertex set \\(V\\) and \\(|e|\\) denotes the Euclidean length of edge \\(e\\). 2. Travelling salesman problem (TSP). For \\(\\alpha > 0\\) the TSP process on the vertex set \\(V\\) with \\(\\alpha\\)th power weighted edges is given by \\( T^{\\alpha}(V):= \\min_{T} \\sum_{e \\in T } |e |^{\\alpha}, \\) where the minimum is over all tours \\(T\\) on the vertex set \\(V\\). 3. Minimal matching. For \\(\\alpha > 0\\) the minimal matching on \\(V\\) with \\(\\alpha\\)th power weighted edges is given by \\( S^{\\alpha}(V):= \\min_{\\varrho} \\sum_{i=1 }^{n/2} |x_{\\varrho(2i-1)}-x_{\\varrho(2i)} |^{\\alpha}, \\) where \\(|. |\\) denotes Euclidean norm and where the minimum is over all permutations of integers \\(1,2,\\dots,n,\\) and where \\(n\\) is assumed to have even parity. \\smallskip \\noindent The key simplifying idea involves consideration of the associated ``boundary'' processes. The approach taken in the paper consists of the following two natural ideas: (i) given a Euclidean process, use superadditivity to find the worst case asymptotics for the canonical ``boundary process'' and (ii) use a dyadic subdivision of the cube to show that the Euclidean process is close to the boundary process.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1375702$96343AFF-B942-49FC-BF12-E4AD86EB1D39","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$10277105-88D3-42A5-AB25-70DD80CEEA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"145b3547074abae69f7ea12a847bac9f122cc911","datavalue":{"value":"52A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$CCE9B637-F2F0-480B-86B9-5D1D4E9DD449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$4D7C39BC-ED52-4199-843B-E59A4AE24B03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a9f118e6d8b9d4481b8d0046969d74cd69a9905","datavalue":{"value":"1102610","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$B6DC3594-1384-442A-954F-6D20FE3AA04F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1375702$18CB7A67-6433-4EE9-B4B6-4D0213C88FFC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"62d639f830e9ae9bae8c47c1f74400b426bd06e8","datavalue":{"value":{"entity-type":"item","numeric-id":1385434,"id":"Q1385434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$39B44F86-DB80-488B-8234-E07F02E16019","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f5406ab0ba27d6c00cf0c439b18ba07997821275","datavalue":{"value":{"entity-type":"item","numeric-id":1412847,"id":"Q1412847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$2C0C310F-A84E-4DCC-A921-15453FE05EFF","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":"Q1375702$C4B0FE52-B4B3-47AA-9CA1-BE7ACCB147C8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ecbadb905930ae081fb4980e3c5f1fcc21a123","datavalue":{"value":{"entity-type":"item","numeric-id":5729634,"id":"Q5729634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$7843070B-5906-4BC6-813C-52D6F6896472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97729ccca9e9ade51cee6873835133e6a361b96c","datavalue":{"value":{"entity-type":"item","numeric-id":1345581,"id":"Q1345581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$8578F80B-81C2-416B-9018-A1CF4289C34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ec6e48ab19fb6ff7b8a743a6e26f7939abffb76","datavalue":{"value":{"entity-type":"item","numeric-id":1915837,"id":"Q1915837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$6071FFB1-AFD1-466B-A235-E2FC3DDCE4B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f396b0fecde991325e5d1c8fbe3ecc7fce878152","datavalue":{"value":{"entity-type":"item","numeric-id":3204344,"id":"Q3204344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$23780E04-5FEF-4E39-8BBB-1C97F1D6EA6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd9c902e18f256ef6ab9ecbbe60131e5487ac544","datavalue":{"value":{"entity-type":"item","numeric-id":1152627,"id":"Q1152627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$CBDC3A68-9D33-4725-8FAF-4498FB7A4882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"093272041b3d9e95afbb499643d38717b589b7a9","datavalue":{"value":{"entity-type":"item","numeric-id":3829359,"id":"Q3829359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$CD59B667-0679-41B5-8235-A3B3BFB8FBFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccd625cdd4a86c4591b00727506148de0499e2e0","datavalue":{"value":{"entity-type":"item","numeric-id":1893902,"id":"Q1893902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$39B13EA4-0415-4729-9220-7950BAEC5BF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dc9a16a78a0ffc1c437f41e10854a7927313c29","datavalue":{"value":{"entity-type":"item","numeric-id":2564700,"id":"Q2564700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1375702$A2C7B36A-66D2-46E7-B3E7-B3E7F5A3CBC5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6260ba584d682a847af7b62f2a9a6ec9a1970450","datavalue":{"value":"https://doi.org/10.1007/bf01271275","type":"string"},"datatype":"url"},"type":"statement","id":"Q1375702$A21BDD08-6354-4F22-A7EB-9E3B6636AF45","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d883f66be0fb743d6e95313100f8c2481c548e02","datavalue":{"value":"W1966155527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1375702$DA5357D2-2788-4FB9-87F2-9CC8F972F391","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e30d1fcd6f142af615f806174c2c1db909dde68","datavalue":{"value":{"entity-type":"item","numeric-id":3829359,"id":"Q3829359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bd5bfe2041371d5b5ba3addfdfe550006bdbba3","datavalue":{"value":{"amount":"+0.8462228775024414","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":"Q1375702$4D804583-7ECC-4BFA-A89F-EBD4B78AEC98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ebd2da6db20b822cbccc54045d3129603f48986","datavalue":{"value":{"entity-type":"item","numeric-id":5749151,"id":"Q5749151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffcfccdba50aaf1d4be4d4e11a57a00ec9428682","datavalue":{"value":{"amount":"+0.8333278298377991","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":"Q1375702$93C10807-3772-4E25-A501-E3458C6DE526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2751b144a7358f1a16d70ccebfacc99bac122829","datavalue":{"value":{"entity-type":"item","numeric-id":3494401,"id":"Q3494401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8290c17ecd771dfcbbdbdf0ad9967bb8fd46f50f","datavalue":{"value":{"amount":"+0.8214132785797119","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":"Q1375702$695A80DF-422F-4005-8469-F714C7574424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35d953e9a1dd889d47c63ba80dd52d66d1124e67","datavalue":{"value":{"entity-type":"item","numeric-id":752004,"id":"Q752004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a648de44667534b42bb229a4ede34b148f1c4deb","datavalue":{"value":{"amount":"+0.8144011497497559","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":"Q1375702$69DBC2E2-FE38-436D-8151-8B351AFA236A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c385c6bee66b2b916aef1a57e0bc168e1890d718","datavalue":{"value":{"entity-type":"item","numeric-id":1849933,"id":"Q1849933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34231cddbcbd7cdcf5d9b67573ac638fe7a4210f","datavalue":{"value":{"amount":"+0.8112615346908569","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":"Q1375702$6BBF7B34-0377-4511-BA77-7D5322CC08B4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Worst case asymptotics for some classical optimization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Worst_case_asymptotics_for_some_classical_optimization_problems"}}}}}