{"entities":{"Q911484":{"pageid":913332,"ns":120,"title":"Item:Q911484","lastrevid":65314122,"modified":"2026-04-12T01:44:22Z","type":"item","id":"Q911484","labels":{"en":{"language":"en","value":"A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4141827"}},"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":"Q911484$1BCB8935-23FF-455A-BD0E-BF211A262928","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14638343838eea91c67135ab87ceb8d0ffc76235","datavalue":{"value":{"text":"A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q911484$84D336B1-E564-4DBE-8AB5-CDB9C2744CCB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e31e400db06c14c4782a10dcd782719ae0ce648f","datavalue":{"value":"0696.90078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911484$3A53224A-E55A-4528-AC01-1DB0BD64848A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"76e4aff632546299a1aeb26f86993908cff3e182","datavalue":{"value":"10.1016/0167-6377(90)90033-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911484$1ECC6086-5D0D-4F9C-9B4F-819C38A8564F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bfeac8e89a9af56cb5cea01287e9f0acc65cc60","datavalue":{"value":{"entity-type":"item","numeric-id":911482,"id":"Q911482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$BE87347B-B6A4-4917-AF3B-1AC6A12CBA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3088059af31cc204d0245bbe3df3eb101fe3516f","datavalue":{"value":{"entity-type":"item","numeric-id":911483,"id":"Q911483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$07273475-0B8C-42E0-A412-F252EC05F1ED","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":"Q911484$C78E3816-0538-4545-B7F3-CD516D1E6243","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q911484$342052DE-B710-4C39-8E5F-E81721011DA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3854b1e76ee44dc7e86192c06cad5546a619bf4","datavalue":{"value":"An approach to the symmetric traveling salesman problem is the 1-tree relaxation introduced by \\textit{M. Held} and \\textit{R. M. Karp} [Oper. Res. 18, 1138-1162 (1970; Zbl 0226.90047); Math. Program. 1, 6-25 (1971; Zbl 0232.90038)], who experimented with a dual ascent algorithm in which the primitive direction consisted of all positive and negative unit vectors, their algorithm consisted of selecting a node that was incident to more (less) than 2 edges in an optimal 1-tree, and attempting to ascend by increasing (decreasing) the dual variable for this node.    This paper presents a generalization of Held and Karp's ascent algorithm, in which potential ascent directions correspond to a set of nodes that is either out of kilter high or low if the number of arcs incident on the set is either greater or less than twice the number of nodes in the set. Ascent is achieved by increasing (decreasing) all dual variables for a set of nodes out of kilter high (low) in all 1-trees that are alternate optimal at the current dual solution.    The experiments on a set of both classical and randomly generated test problems up to 100 cities show that the dual ascent algorithm produced near-optimal bounds in about one-quarter of the time required by the subgradient method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q911484$4E56D2D2-D50C-4F7C-BBA8-6EC48902547B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911484$F11EFB79-DE26-492F-AB1D-F651B69C8564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911484$C7D3DB0D-3650-4066-B493-C4B99E9602BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"420c27d55d1630a424469a85395fd31c1d4ac38f","datavalue":{"value":"4141827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911484$5A8E2D16-8AFE-4D57-9EB0-0A1DCCBE1CB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"380418f9694f7a498c4c86d6efdeb1edd87aac4b","datavalue":{"value":"symmetric traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q911484$31BC5B00-85DF-4170-ABE6-51E537F8E30E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f61975a92a0dec3c1b39f7db2caaaef61ecb0f72","datavalue":{"value":"1-tree relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q911484$27679C63-DC5E-4277-A41E-FDF16F97342F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66109680e9d2cb13156b85afb98e633f45e988bd","datavalue":{"value":"dual ascent","type":"string"},"datatype":"string"},"type":"statement","id":"Q911484$57503A10-D593-45E7-9360-B5508A1BB2C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7cc89d47b01aab01384f4b5b0ef290f9e82efb7","datavalue":{"value":"out of kilter","type":"string"},"datatype":"string"},"type":"statement","id":"Q911484$0CFA2457-4CBA-4761-A7F7-FDF1EDFA60E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4194ddc89ecfe5fc55518b6f584d663a167ba1e2","datavalue":{"value":"subgradient method","type":"string"},"datatype":"string"},"type":"statement","id":"Q911484$7C2AA147-9386-4252-BDFF-783F4CA5255A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f8851f7d7ed4147f596ab1e98283df373347f7d6","datavalue":{"value":{"entity-type":"item","numeric-id":180312,"id":"Q180312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$8B10D839-1E17-4E86-AB62-129D9F3A3F99","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":"Q911484$E25DE829-575D-493A-ABDF-8DB8BCAAAD73","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7d2adb85493bb31fc75785df774d6fb05fb5d6d","datavalue":{"value":"https://doi.org/10.1016/0167-6377(90)90033-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q911484$8C1330AD-8D6F-4A60-AEF8-2824B553F1E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9e993ffd1493afb96a3218d6cd042c1827d3bad","datavalue":{"value":"W2009084435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911484$F309DCAB-EC81-4A89-B792-75BD80D5E6AF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde83dc2358b044be23eaeb3226ac019d5e33e09","datavalue":{"value":{"entity-type":"item","numeric-id":5378639,"id":"Q5378639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$9636B207-CC69-48A2-8236-3CB055793515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70402ed7657981108854cf14b63a1a4fdf284f66","datavalue":{"value":{"entity-type":"item","numeric-id":3856429,"id":"Q3856429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$E9276D35-0EB4-4ADF-A266-45D02FCC62A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083d97e730faf90a4132402a3f045bdbf076bc3c","datavalue":{"value":{"entity-type":"item","numeric-id":3919449,"id":"Q3919449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$371D965C-25E3-4BE3-A796-6E17C6C76453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212f07c415ef8012848f935f837361eec248c785","datavalue":{"value":{"entity-type":"item","numeric-id":3030567,"id":"Q3030567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$A7756612-9314-42D6-8535-1166DB1862D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f73eb84a543b338a4a079febb7b97c03a91da92f","datavalue":{"value":{"entity-type":"item","numeric-id":5633847,"id":"Q5633847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$0CA91E4A-2312-4CBE-BFAF-BE2CB6509F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$11C32105-3DA9-4158-BCB5-33E459B58AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$32BA33F4-8C33-4EDF-89A4-34B694BBF125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8634671064abab94a7b8dbe7f85bfc42274b7db2","datavalue":{"value":{"entity-type":"item","numeric-id":4770776,"id":"Q4770776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$5067BF15-61E6-4E66-A120-4C81C168DB65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18ae18b7fecfabff69866f0aaf6dcb21169b193f","datavalue":{"value":{"entity-type":"item","numeric-id":4132264,"id":"Q4132264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$10BD4BFF-3909-4F57-ADB6-28B2F00DDC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb4bb8ecc53694b95953f765733c32a872021462","datavalue":{"value":{"entity-type":"item","numeric-id":3048273,"id":"Q3048273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$9CA096D0-02D1-431E-A913-EC9337EB4B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d50c47177046856485cec7a57ce2756a050acbd","datavalue":{"value":{"entity-type":"item","numeric-id":4146571,"id":"Q4146571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$36057140-16F5-4620-8285-501E17AA964D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0650311eaf58d9e1d131a542ba976b8f0f792dfc","datavalue":{"value":{"entity-type":"item","numeric-id":3315294,"id":"Q3315294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$D493E324-27E8-4259-9C48-59570D12E569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f01ec71fc838b01b7cd0695eebd81ce4dcaf7f","datavalue":{"value":{"entity-type":"item","numeric-id":5621270,"id":"Q5621270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911484$9704AE98-509F-42F6-A1E3-64619DEC339E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bce0bee63e7097bf89c74e8a3c654ca5afe7e3eb","datavalue":{"value":{"entity-type":"item","numeric-id":1083379,"id":"Q1083379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf665d26a699757500b62ddf0f4496ef081f9899","datavalue":{"value":{"amount":"+0.8004589080810547","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":"Q911484$1B710967-4947-4399-932F-D56FDC588524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39319402a34a0167b34a96f8ad3ca3e5221e1edc","datavalue":{"value":{"entity-type":"item","numeric-id":4006123,"id":"Q4006123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"227f6f07cd53383184d05a62346ad1461ed0faee","datavalue":{"value":{"amount":"+0.7925823330879211","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":"Q911484$7283D8AA-EC6D-44EA-ADAC-B3352BEBD029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421a44ea561d12439ee43f24359b2ee644067542","datavalue":{"value":{"entity-type":"item","numeric-id":1671016,"id":"Q1671016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91bd6e26342ca45f31562ce8fa38d6836fe9d301","datavalue":{"value":{"amount":"+0.7881215214729309","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":"Q911484$4FA4B5FC-9DD6-44A6-8CCF-BCF45B94D0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41fec4d1f4d350ec6a9592eea71f209c90cc59b6","datavalue":{"value":{"entity-type":"item","numeric-id":1281074,"id":"Q1281074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ec92423fc7af529c1c1ca5d7b2d37b7ef5c54d3","datavalue":{"value":{"amount":"+0.7859604358673096","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":"Q911484$F985CD12-0C10-4B47-B0A0-EE22C16C3587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c53f67e79b769ee6a27ad6e0589f54bae1c887a","datavalue":{"value":{"entity-type":"item","numeric-id":4371607,"id":"Q4371607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"250dd2bc0521fe4bdfc88bbb7b1e2313e601478e","datavalue":{"value":{"amount":"+0.7824723720550537","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":"Q911484$0309C1B1-1B03-4818-B03E-B45DA7E88BC0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_dual_ascent_algorithm_for_the_1-tree_relaxation_of_the_symmetric_traveling_salesman_problem"}}}}}