{"entities":{"Q649110":{"pageid":650959,"ns":120,"title":"Item:Q649110","lastrevid":51376721,"modified":"2026-01-18T00:05:00Z","type":"item","id":"Q649110","labels":{"en":{"language":"en","value":"Approximating the metric TSP in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5982660"}},"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":"Q649110$30AAE839-A491-4F83-8488-B75F2FD91ED8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3170967600e2032fcf9971c83fe622548e121584","datavalue":{"value":{"text":"Approximating the metric TSP in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q649110$596E06D6-0760-45B3-9DEF-D7227BBD0EB7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11972bed6e892efb11a9cf5a2b57c977f0b16483","datavalue":{"value":"1227.68029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$3B03DB9E-A83E-471B-8573-C8ADDBB0BAF8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e83bdac08dc37c8b4e4e1d65ab2347392b9940c0","datavalue":{"value":{"entity-type":"item","numeric-id":338389,"id":"Q338389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$1B96DBBB-A776-4D3D-BCFC-5246D49D5696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8da87037f18739fb6ba13a01513f17ad10a2cf73","datavalue":{"value":{"entity-type":"item","numeric-id":649109,"id":"Q649109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$AEFE36D8-4C1D-4B7C-A339-1B1ED683731F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eaa49266994fffdf55051342d8ff9a32f6e64e65","datavalue":{"value":{"entity-type":"item","numeric-id":293312,"id":"Q293312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$4502F59E-FF14-416E-9A7F-6F756A176E86","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$F590EA0D-6E3A-418E-8ADB-418117A96C70","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1819a172538b9934d4c5de27188f75c7b63afe97","datavalue":{"value":{"time":"+2011-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q649110$BA13BBED-D7C6-4759-8B08-241EBD310778","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$C3B07D4D-0DF7-4418-85C9-14119051FFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$7FEF60F8-6176-4CE9-AF8C-8DF677075F07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$F9788772-C4D4-4435-A69B-8CE146466406","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"89d8145a16b46aea7563d013dbb6c4eaedb13208","datavalue":{"value":"5982660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$2D4DEC4E-5F75-45B0-ADCF-12E53DFF3A52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"398999db83e6f0b9619e9606c6c09b8be1baa252","datavalue":{"value":"traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q649110$2595CF9E-148E-4604-A98C-807954EF1DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f846e508f896e84815a66ef2d2f886494d23347e","datavalue":{"value":"metric graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q649110$D7D98BC5-959F-4CDD-B287-D99E92C9A8D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q649110$F89B1D0F-A29D-440B-9077-A189D2EF99BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21f3709a23b8492554be8c311a1cc1313373c706","datavalue":{"value":"linear-time approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q649110$22FF1A30-A383-43D5-882B-D6D3DA3B40C3","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7237258b836283bef33e897e128d37db9d627348","datavalue":{"value":{"entity-type":"item","numeric-id":13727,"id":"Q13727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$CA3A632D-BBEE-433A-B649-D31E59A3E53D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"239a282aac0e1427d1a5133886fbf7115bab5f39","datavalue":{"value":{"entity-type":"item","numeric-id":16936,"id":"Q16936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$5669A4AA-5EC4-4CF1-BD0E-714E3CB1F733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"861b6656f2af5b4e36266a088688f5b50caee033","datavalue":{"value":{"entity-type":"item","numeric-id":16943,"id":"Q16943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$E8DBBB34-3DC7-458C-98E9-6ED69D688DF2","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":"Q649110$4EDAD100-8D10-435B-A33C-74765F2C8760","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"711fbb592b1784a4c19d797e28d553cb7547ae06","datavalue":{"value":"https://doi.org/10.1007/s00224-010-9289-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q649110$46684635-D692-4311-B7D5-C11A78469D9F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c07a25a7cf248eb48dcebdd81f4903665366db43","datavalue":{"value":"W2054572608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$089927E0-9125-4E68-89D3-EFEE5C315B15","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a29d77c4b142496ea1b85cfa950b11782eee28b8","datavalue":{"value":{"entity-type":"item","numeric-id":2748380,"id":"Q2748380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$B6A89E08-700D-41EA-86B0-6624DEEC446E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc3521bcb8d659481e51183e64ccc0a7ef49d267","datavalue":{"value":{"entity-type":"item","numeric-id":3158519,"id":"Q3158519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$B44DA834-F39F-43B6-B89E-4C63E59B9A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a16cba46842547510341ff68e66da160da533bb2","datavalue":{"value":{"entity-type":"item","numeric-id":4501548,"id":"Q4501548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$B57E3D40-D3C0-404C-BC44-E9C6FE08CBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f335709cafac8ad70fda23558eac5858cccfcd82","datavalue":{"value":{"entity-type":"item","numeric-id":2757553,"id":"Q2757553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$C643812C-4B01-4D07-9925-81A15629440A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecd3cb20dc5d80d39db32e8cbb8a990ee7f2f21c","datavalue":{"value":{"entity-type":"item","numeric-id":5432314,"id":"Q5432314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$BB84F665-D271-4185-A601-BF3152FA9A36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0990131407686e7f541811df32da71de6145a731","datavalue":{"value":{"entity-type":"item","numeric-id":5406222,"id":"Q5406222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$707A23E9-27A4-4B02-AF4F-5062C885EDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"237754f927e402be4f4fe64c1d99c9d4cfd28e97","datavalue":{"value":{"entity-type":"item","numeric-id":2839206,"id":"Q2839206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$11DFB88D-8CE6-4452-BE00-2110A22ADDD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6204e56589df344691ffc7534bf94bce6a69259a","datavalue":{"value":{"entity-type":"item","numeric-id":2944492,"id":"Q2944492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$6275EFF3-A312-4B34-8B50-CBBAF8F92826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fa963d9e59691da5d6545fdb4d42ce2b1a1cd5a","datavalue":{"value":{"entity-type":"item","numeric-id":4302856,"id":"Q4302856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$1E88AC79-CAED-46C2-BA9B-840214599D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a3584ce3be960bc4e122ccc96f46a8dd4ee24b0","datavalue":{"value":{"entity-type":"item","numeric-id":2819576,"id":"Q2819576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$F42361CD-5792-43EA-99AA-3559F3DA2FD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73a0e2c48c3ecc4ffb0e6cdfd57c4cb2e6570ff3","datavalue":{"value":{"entity-type":"item","numeric-id":734352,"id":"Q734352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$D72C24C8-B24C-4BEA-9A69-A0A4ABD1AC15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c059d95de4987158e8b3b55fb5d1d1cdc22ec2","datavalue":{"value":{"entity-type":"item","numeric-id":2495698,"id":"Q2495698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$B3438C55-B3C2-4A54-8E57-3F32117B7DA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48b538f59fa79437abf1147a3e501cd84d06d7c9","datavalue":{"value":{"entity-type":"item","numeric-id":4697080,"id":"Q4697080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$F2DB45FD-E8C3-43B3-AE95-9E0DE5CABAB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03d848b0164f348d2c91ca9fce279a81455334a1","datavalue":{"value":{"entity-type":"item","numeric-id":4015422,"id":"Q4015422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$1A42CC07-1078-48DE-9E30-3F6A4AC8B4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6a594a255360f75d93bb8ec3ef4752302b651bc","datavalue":{"value":{"entity-type":"item","numeric-id":1427191,"id":"Q1427191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649110$E16D18B7-EB80-4DA9-9B5A-9FFC4E6C9DF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e680552a4f0423b621c1bc066e10c714e24ab1fb","datavalue":{"value":"10.1007/S00224-010-9289-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649110$8C2D843E-7B28-41D3-BBBE-0E491D04C602","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2ab9820cf087aacb54b6c1c43100d9d0a99db54","datavalue":{"value":{"entity-type":"item","numeric-id":5302042,"id":"Q5302042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ca7e9084265dd5cb9041ec420ab6fee9ed8fdae","datavalue":{"value":{"amount":"+0.9899864792823792","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":"Q649110$34EC507F-BA85-4103-897F-ECA76CDC7D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"840244e18f8c54fe34fa268d5f49970b35c9174d","datavalue":{"value":{"entity-type":"item","numeric-id":5406222,"id":"Q5406222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7be8cfc68fdfda64d7c0922088357a72ec597d93","datavalue":{"value":{"amount":"+0.8253703713417053","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":"Q649110$C4113099-AE6D-4415-A82F-471DD1DC85C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0792f8a43c0ea0c1b6770e01ba77ae2e60676888","datavalue":{"value":{"entity-type":"item","numeric-id":5475830,"id":"Q5475830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b4ad0931131ccd72e5788a8823c18095f197ff6","datavalue":{"value":{"amount":"+0.8244423866271973","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":"Q649110$AF4EDBF1-3955-4D04-9F87-3A650DCF39E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b670986bdfe95dbd70bda179a9619758caa354b","datavalue":{"value":{"entity-type":"item","numeric-id":4501548,"id":"Q4501548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d474187146a85911ac2f8d13b2f2e9ecc7a1858","datavalue":{"value":{"amount":"+0.8238124847412109","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":"Q649110$AF856B4D-2D57-4DEB-90A5-B57431CEF167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c176da7cee0a1f88a8aeabb10b35d7cd0cdd8bd","datavalue":{"value":{"entity-type":"item","numeric-id":1034619,"id":"Q1034619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d474187146a85911ac2f8d13b2f2e9ecc7a1858","datavalue":{"value":{"amount":"+0.8238124847412109","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":"Q649110$B65C2CC5-2B81-4645-A0D2-477A814CBE9A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:649110","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:649110"}}}}}