{"entities":{"Q1885277":{"pageid":1896019,"ns":120,"title":"Item:Q1885277","lastrevid":69190464,"modified":"2026-04-13T05:21:49Z","type":"item","id":"Q1885277","labels":{"en":{"language":"en","value":"On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2111486"}},"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":"Q1885277$4B181355-2D01-4BE3-A168-752824B0E9EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e1154cb1b2e5f369334684e576487f1588b89be4","datavalue":{"value":{"text":"On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1885277$9A74FB52-50D6-40CB-AA55-F2EE65ACE55B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd1d6a9c28bc5cf6197e569f971799267c92c413","datavalue":{"value":"1136.90031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$A44F4220-2749-4154-979C-D3737EDDF882","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1885277$ED6D7750-6FC7-4682-9AF2-25D63EFC0B4C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1885277$84565034-8934-4C7D-91C5-1D5A0BB6760A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"537531571b4f861519c1304a6e93493bd9f1a450","datavalue":{"value":{"time":"+2004-10-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1885277$1B746C7C-255C-4712-AE6B-6288FBE9B481","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"401eb4d27b076c088efe4d9042b9608ca564c96a","datavalue":{"value":"The paper interrelates the approximabilities of the metric STSP (Symmetric Traveling Salesman Problem) and the metric ATSP (Asymmetric Traveling Salesman Problem) via the Held-Karp linear programming relaxation of the metric STSP, for which an integrality gap of \\(4/3\\) was conjectured. Using a new characterization of the integrality gap for general linear objective functions over polyhedra together with the definition of ultra-fundamental, hard-to-round STSP extreme points, it is shown that a slight strengthening of the Held-Karp conjecture would imply also a tight \\(4/3\\) integrality gap for the metric ATSP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1885277$F53B39FD-0D36-4414-BED4-5C47485FAC55","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cd82a38b4fa9f2b7fd7dde601f94fd2c96d5a6ee","datavalue":{"value":{"entity-type":"item","numeric-id":227996,"id":"Q227996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1885277$4C30F012-A2AC-40F7-8FFB-73E8449F6701","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$F3BF570B-3CEA-435B-9E60-8C3B55275E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$6B51DBF3-A36C-4017-830C-00176EE90168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$C2B1F538-7CFF-47E8-BB25-FC4B42093783","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"991a54b948f6fc5673f5bdb2c3aa388cc65439ca","datavalue":{"value":"2111486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$229163A2-EA21-40AB-8479-7D83F9BAF4F2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97339565def2592a07038417be073b47fb6235f5","datavalue":{"value":"ATSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1885277$9FC13DC8-F68F-4921-BC36-0CE485E55190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22b1e8aec7a874a2c665d4668941cc379ca9ff73","datavalue":{"value":"STSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1885277$F6CEB762-68AE-4F80-999A-E846152AA48C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"533ed66c7e237697c722dc21b6ca1bb7999c060c","datavalue":{"value":"Held-Karp relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1885277$BD07D399-F164-4F08-A95C-DD21756842F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2c99e1e4a257fbb96c7487cd27964c594e30a89","datavalue":{"value":"integrality gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q1885277$91F0B799-3280-4A14-B0CF-5FEB9F1DD98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1885277$8B82B653-8B03-4091-B2FB-FFEEA1CBB4DA","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":"Q1885277$A2428C82-7DB8-4407-AF0F-D02B839AD001","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4337cf2f7330f7fb3d3719ef636e69216d44136","datavalue":{"value":"https://doi.org/10.1007/s10107-004-0506-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1885277$6C831704-C73B-4A62-AAC2-8381D5E7A294","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3730222bce6042b56f345e96205d42132a8b33bd","datavalue":{"value":"W2038458261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$A4357D9C-E6DA-41AB-A0FD-8FBC5647ABF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f7ef26ce293a03fddb2d03601cb4063d3426d31","datavalue":{"value":"10.1007/S10107-004-0506-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1885277$1F882A4F-F47E-46C8-B4A5-84427325D5BB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"953816ae7d953f86113bd4d5a15fbd329b0145ec","datavalue":{"value":{"entity-type":"item","numeric-id":4952607,"id":"Q4952607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba47ba7ff08846bba309f9e026e808e5531f91fe","datavalue":{"value":{"amount":"+0.8868908286094666","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":"Q1885277$CD7BB9D4-8C0A-4AE6-95AE-DDBA898B0A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b22acad3e0c293fd33aa047e97502bfe31f18376","datavalue":{"value":{"entity-type":"item","numeric-id":3541797,"id":"Q3541797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"689fdc32ff69979d309dea429589c67199892022","datavalue":{"value":{"amount":"+0.862302839756012","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":"Q1885277$065BA5C6-C7F8-43CE-94C5-FCA7492E859F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47f6cdcc366218457db1fa6130caa2a438c93bc2","datavalue":{"value":{"entity-type":"item","numeric-id":378136,"id":"Q378136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b58f4c4bc48ac71e238addc12f54b38c55d3fdd","datavalue":{"value":{"amount":"+0.8150184750556946","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":"Q1885277$1D7D46D7-8CF3-4A77-8CC7-7836ABA2E3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae1bfe2eb05fd9eae3d513929da67257359d5281","datavalue":{"value":{"entity-type":"item","numeric-id":1200770,"id":"Q1200770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55da6ac29f54a71b0504afb68e373c53d6ca5818","datavalue":{"value":{"amount":"+0.8080469965934753","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":"Q1885277$8934CCE5-4C83-4371-958C-DF7BB41BF1B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_Held-Karp_relaxation_for_the_asymmetric_and_symmetric_traveling_salesman_problems"}}}}}