{"entities":{"Q1180833":{"pageid":1191582,"ns":120,"title":"Item:Q1180833","lastrevid":66779751,"modified":"2026-04-12T12:48:24Z","type":"item","id":"Q1180833","labels":{"en":{"language":"en","value":"Analysis of Christofides' heuristic: some paths are more difficult than cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 30036"}},"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":"Q1180833$C717506F-79A3-483B-B48F-B8DCD936B810","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2c8621e98ef4a4147643c8e1314a0fe25e786f1c","datavalue":{"value":{"text":"Analysis of Christofides' heuristic: some paths are more difficult than cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180833$E6939C89-DD66-40FC-A46C-FCC73D638AC8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2feb7d13fe465ec6b14143d2994e8530cf9b1845","datavalue":{"value":"0748.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$137BD9FE-38B7-4A82-BDE1-788635E10155","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28f8ff245bd33f73a5d8036b2ac57d8debd86712","datavalue":{"value":"10.1016/0167-6377(91)90016-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$F76B1E48-ED43-4AE3-8B99-06535EBFA0CE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180833$A4BF65C8-73A2-4C81-A946-24866E2D0B15","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180833$9BAA0375-5F5F-4170-9F29-A2E3322FE653","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23ba4c8e421c7a0f0ac013ff3a0f34b43925210b","datavalue":{"value":"Christofides proposed a heuristic for the travelling salesman problem in which the distances satisfy the triangle inequality that produces a cycle with a length that is less than \\(3/2\\) times the optimum cycle length. The author deals with the problem of finding a Hamiltonian path of minimum total length with zero, one or two prespecified endpoints and formulates Christofides-like algorithms for each of these three problems. It is easy to see that the heuristic is still a \\(3/2\\)-approximation algorithm for the problems with zero and one endpoint. For the third case the worst performance ratio is shown to be \\(5/3\\) and it is shown that this bound is tight.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$88031B0D-87AF-4465-9D3F-E190AF0F8BA9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$BF707029-C875-4948-9BE6-FE56E02DE7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$6B67C507-8C9B-4D89-AA0C-31EFAB896C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$965D3CFB-080F-474F-BB85-6AACAA0E586A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86c7877baefdab7d53c9c67a0dcbf6602c06e553","datavalue":{"value":"30036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$BC58A862-B684-467A-BCDE-8D1B1B2BFB44","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14f5692e185b1488dd97e357834d4b024a1d4fa4","datavalue":{"value":"worst-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$B437417D-6B1A-4CF1-9CF0-71C3DA102235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$6945F0B3-8575-43D3-A277-6678D696A9BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$5BB7FDA6-C5C6-45B7-9211-C0171C7A91C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f340e09d34947a12bf0542f03dfce1436c5f2a28","datavalue":{"value":"minimum total length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$E1750275-63DD-4ED8-AECB-B1BF3C4A80D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada3d68fced84646ef9e9acbb221b70baa63288a","datavalue":{"value":"Christofides-like algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$C1AE33CB-331C-4500-9657-0368EA226CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180833$2FABC6B9-C6EE-42F1-90CF-0E8D622AECBA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0eeb9005f15747f7691d1f0f8c3da9f051f98145","datavalue":{"value":{"entity-type":"item","numeric-id":161973,"id":"Q161973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180833$FBC5A270-9658-4F95-B3CC-5DFE6E58FA06","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":"Q1180833$09EF475D-06A7-4E95-8B48-28C03BFE6679","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1207e6aa1fc06e1913a02d7555e24510b78299db","datavalue":{"value":{"entity-type":"item","numeric-id":4744064,"id":"Q4744064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180833$C8F6FBFF-A671-4F7C-BA80-433F00200214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73d686f615f922e2736c2847ac6f0f364609a64f","datavalue":{"value":{"entity-type":"item","numeric-id":4180168,"id":"Q4180168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180833$62990DCD-2F8F-4DDC-A703-C24FDA649F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a96c989d90e2e2902db5020c0cdff50569413a7e","datavalue":{"value":{"entity-type":"item","numeric-id":3693290,"id":"Q3693290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180833$993F21E2-59B4-4592-BD67-FE5D43170409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf376f2946131481bf0c634e0ff1ff4924c8e63","datavalue":{"value":{"entity-type":"item","numeric-id":4119042,"id":"Q4119042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180833$ACF0259D-70A4-422B-A84B-1938B2CD8CC7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"54ad7aa58a750aee5d04460a5b0df1948208b546","datavalue":{"value":"https://doi.org/10.1016/0167-6377(91)90016-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q1180833$89EF9514-2F37-4ED8-81AF-171926FFD0E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd2c143b151efc9db88b14aa519b8d3365af8df3","datavalue":{"value":"W2162750432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180833$3676B841-C4BC-4A9C-B00C-05299895B860","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76cfd0483e6a41af0e1f5e5393879c240a16f478","datavalue":{"value":{"entity-type":"item","numeric-id":2120141,"id":"Q2120141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2f838eec02898e84bd8cfc97b7b73bfe760e969","datavalue":{"value":{"amount":"+0.8450512886047363","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":"Q1180833$1E022A2A-F21E-4A51-B582-8F025A7A52E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2c617a24c82cb23f1830ab85ee150f05366eb13","datavalue":{"value":{"entity-type":"item","numeric-id":3415353,"id":"Q3415353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bf1dd8d00fa38fbbb7051f757694366d27cf138","datavalue":{"value":{"amount":"+0.8085052967071533","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":"Q1180833$85A75F4B-3D7C-4A5B-A832-4ACE2E468F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66499fdaae6ef83717bb12300d4d7be60f3eef22","datavalue":{"value":{"entity-type":"item","numeric-id":5711527,"id":"Q5711527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"122a4bce009062f91423e1091ff418cc63c04a41","datavalue":{"value":{"amount":"+0.8064853549003601","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":"Q1180833$216B7720-0892-467B-A793-D731D2307E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97146612761237142c692504f981f112fa337a1c","datavalue":{"value":{"entity-type":"item","numeric-id":2904559,"id":"Q2904559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc8d67e68a3d8b0655dfdfb7a9b1349fe3d25a65","datavalue":{"value":{"amount":"+0.8039659261703491","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":"Q1180833$8A5FD654-4466-417A-A71A-01312D372EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f735ba9b39faec3b9c8b05006427ce465788e439","datavalue":{"value":{"entity-type":"item","numeric-id":3337225,"id":"Q3337225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb024e7e1edf6a03b14ed5a47ee47a8f28aad92b","datavalue":{"value":{"amount":"+0.8039389848709106","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":"Q1180833$A56569B8-E2E6-40EB-A3AA-A66DC7907C61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analysis of Christofides' heuristic: some paths are more difficult than cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Analysis_of_Christofides%27_heuristic:_some_paths_are_more_difficult_than_cycles"}}}}}