{"entities":{"Q1196167":{"pageid":1206916,"ns":120,"title":"Item:Q1196167","lastrevid":47098117,"modified":"2025-12-31T16:16:48Z","type":"item","id":"Q1196167","labels":{"en":{"language":"en","value":"Tight integral duality gap in the Chinese postman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 77838"}},"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":"Q1196167$D66BE93F-3A6B-484E-B6F0-D388AE318E94","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"79694d0af7299befd17c0a39b5854c206191302a","datavalue":{"value":{"text":"Tight integral duality gap in the Chinese postman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1196167$CFB5B99C-91A9-4437-B58A-1BCBC9E5C16E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c8847adb375199e1ab22f688adbee81e9fd60ba8","datavalue":{"value":"0767.90088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196167$42196580-9899-4D4B-BD69-055B77198192","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a16f0cf0d70c9ff725e24e80dde2b99775035db9","datavalue":{"value":"10.1007/BF01581198","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196167$B18002C5-B583-4C58-A3B3-488F7680FF50","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d049f32d9c5057f44701109662e613026b41055","datavalue":{"value":{"entity-type":"item","numeric-id":216241,"id":"Q216241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$D629ACA4-EBB5-4FC9-B52C-459D67E3E56B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a87e85e60300a8c1d2afdced9a1866ffb3d79919","datavalue":{"value":{"entity-type":"item","numeric-id":210307,"id":"Q210307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$D794865B-3F84-4AAE-8A04-9F9CE08472D1","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":"Q1196167$E1F0860C-4672-465F-A7AC-3207C467B40A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8042fe0599241970cf427c9ca68a1764be1ca806","datavalue":{"value":{"time":"+1992-12-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1196167$8F858DF4-4B7D-47AC-BC84-7C7C17FD7BAE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"112611a766a263d154d1faaa49ed7bf2bb3a216f","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph and let \\(w\\) be a weight function \\(w:E\\to Z^ +\\). Let \\(T\\subseteq V\\) be an even subset of the vertices of \\(G\\). A \\(T\\)- cut is an edge-cutset of the graph which divides \\(T\\) into two odd sets. A \\(T\\)-join is a minimal subset of edges that meets every \\(T\\)-cut (a generalization of solutions to the Chinese Postman problem). The main theorem of this paper gives a tight upper bound on the difference between the minimum weight \\(T\\)-join and the maximum weight integral packing of \\(T\\)-cuts. This difference is called the \\((T\\)-join) integral duality gap. Let \\(\\tau_ w\\) be the minimum weight of a \\(T\\)-join, and let \\(\\nu_ w\\) be the maximum weight of an integral packing of \\(T\\)-cuts. If \\(F\\) is a non-empty minimum weight \\(T\\)-join, and \\(n_ F\\) is the number of components of \\(F\\), then we prove that \\(\\tau_ w-\\nu_ w\\leq n_ F- 1\\).   This result unifies and generalizes Fulkerson's result for \\(| T|=2\\) and Seymour's result for \\(| T|=4\\). For a certain integral multicommodity flow problem in the plane, which was recently proved to be \\(NP\\)-complete, the above result gives a solution such that for every commodity the flow is less than the demand by at most one unit.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$5A0C675F-31C9-413D-8CD9-B47145A8EB53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196167$97A84FD7-DE83-47A4-A635-3ABAF9D8DE36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196167$427E8166-4B2B-4126-B6C1-7F641304C008","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b4cf832cdb296e1f49d629f76875f15a6ae57b4c","datavalue":{"value":"77838","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196167$2E30CC4D-3E79-40F2-B503-47DA5F726048","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3e4a080961e9d997a8b36f055c2ccdc6405d2fb","datavalue":{"value":"chinese postman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$A48D4B71-FB84-42BF-BC82-6CA3212A30E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"081fe801f1688e6be5ed08bf6f1da1895499df6c","datavalue":{"value":"\\(T\\)-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$8701A24A-6A45-4355-8865-63C392E73C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48718300b33f06a05d2d0c48885ff4863d87633a","datavalue":{"value":"\\(T\\)-join","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$37422107-1518-4FA3-92FD-2E17916DF037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47a5d1753a95eb2a34d4636d026e08b58609fb3e","datavalue":{"value":"tight upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$6F5903FD-EDA6-4580-8EC5-25E498ADCFD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae227d6ff6678b73b6bb0b87bf256711fdb32c3","datavalue":{"value":"maximum weight integral packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$792C131E-0A16-47B6-8034-89C37DE2F1B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c48e481c2d75f1350db75037c097d2db1b68956","datavalue":{"value":"integral duality gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$911B0851-7813-457D-96BA-E0C8F9A7DA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0affe942f4bab1f7d6a2da1658e29d8bbce2ad05","datavalue":{"value":"integral multicommodity flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196167$14D733D8-A85E-4184-BB07-10C8CFB68DB1","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":"Q1196167$38A2BCFE-ADB8-493B-ACE3-E1DDECCD9028","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$FDDC935D-6021-4894-8E8C-B80769D19EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d51cc64185b2e669f7f17dc476c769ec0ad4ed5","datavalue":{"value":{"entity-type":"item","numeric-id":4197644,"id":"Q4197644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$670CEC32-6096-4AC3-9C70-67CB36682372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271059027ec9c0e0491187496cb25dd92d2df81b","datavalue":{"value":{"entity-type":"item","numeric-id":5675543,"id":"Q5675543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$D4292435-0C1F-4EF0-BAC8-D8B0383412D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$2534DAA0-3026-43FD-A558-D4ADDEC0417D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$2D21FF1D-1CA0-4A65-896F-2DF01936B71E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f70d362cfa7331a9394c39182700aab103850eb0","datavalue":{"value":{"entity-type":"item","numeric-id":5572841,"id":"Q5572841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$BA3E1E6B-9935-4172-BE78-B6991F56BAAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fa952bb9270da1543dd8b017183c187354491c1","datavalue":{"value":{"entity-type":"item","numeric-id":1196167,"id":"Q1196167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$6CB37B8B-A821-4165-AD75-53EE48D65532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6dfa3f920ab16949a508ca8ac1782b38c4a9235","datavalue":{"value":{"entity-type":"item","numeric-id":4106238,"id":"Q4106238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$7F07A5B4-0756-4210-9148-B7685D472779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c04be35391516baccbffe6dcb0b18074608ddb4","datavalue":{"value":{"entity-type":"item","numeric-id":2367446,"id":"Q2367446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$B9EE5445-051D-4E5A-AE2C-D0EF7CA2EAFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55583b3306bbbf28eef236672f59a685a07a60dd","datavalue":{"value":{"entity-type":"item","numeric-id":1099186,"id":"Q1099186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$068268B0-39B2-450F-AC14-069E29CB564E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"119d14273a5178c9fdb0109f5da7d88db66c689c","datavalue":{"value":{"entity-type":"item","numeric-id":1245970,"id":"Q1245970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$263A703A-5701-4854-9B29-D0EEC500B545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d93131d3cdff5a369acc96e6fde7360525e3cc8","datavalue":{"value":{"entity-type":"item","numeric-id":1161527,"id":"Q1161527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$0D4580E1-2236-49DB-8531-A99C4D2E37AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91a8a92ba35c4b35ad666b6243007947ecb459ec","datavalue":{"value":{"entity-type":"item","numeric-id":3893626,"id":"Q3893626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196167$9C15BE1A-7EEF-43DC-A3B1-A041CF9B1638","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bc3797b30413712f56acb64531328c05c937333","datavalue":{"value":{"entity-type":"item","numeric-id":3973411,"id":"Q3973411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ada6a28dd5cf1835ec217c724cd25ded3e9daea","datavalue":{"value":{"amount":"+0.8389706611633301","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":"Q1196167$969C357E-5A42-46B4-AF00-9A7851E6B3A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff62b7290c559f74acf59a72903432805fe41d33","datavalue":{"value":{"entity-type":"item","numeric-id":1896345,"id":"Q1896345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff825c486227ed13d34563d8f568ad37d9da25a9","datavalue":{"value":{"amount":"+0.8389705419540405","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":"Q1196167$6F7D1C8A-F15A-4C04-B809-A9FDFFD443E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a3e2f57457d5321282cea783d8d2f4438ddb300","datavalue":{"value":{"entity-type":"item","numeric-id":1089008,"id":"Q1089008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f547093f35d889d1f0665cc2bc4ea9366632b68f","datavalue":{"value":{"amount":"+0.7889905571937561","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":"Q1196167$7FC25AA4-E162-4913-A26C-E094B30BAF59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39aed4bcb8c060434fdd3e20ac1d7a7baf3608b8","datavalue":{"value":{"entity-type":"item","numeric-id":3360020,"id":"Q3360020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d538d6f0c3658220097cc5fc597bc4e2d070d3a","datavalue":{"value":{"amount":"+0.7865584492683411","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":"Q1196167$248C10C2-48D4-475E-B0AB-AFA7A15632A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8494ac424dbba0e1c684ea610b051e7d7ca5609a","datavalue":{"value":{"entity-type":"item","numeric-id":1333320,"id":"Q1333320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a34b36482d9bf4ec36007ae68dce0bfac46bc7fb","datavalue":{"value":{"amount":"+0.7843020558357239","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":"Q1196167$2DC8C766-DC2D-4A94-8263-1FF3FE8DD037","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1196167","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1196167"}}}}}