{"entities":{"Q139206":{"pageid":140739,"ns":120,"title":"Item:Q139206","lastrevid":47111851,"modified":"2025-12-31T17:24:50Z","type":"item","id":"Q139206","labels":{"en":{"language":"en","value":"Approximation algorithms for three-dimensional assignment problems with triangle inequalities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 94374"}},"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":"Q139206$4C2E0C59-B741-42CE-9E11-498880B2CE74","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$52A21538-D3A5-4B27-BAE5-A0A49AA4C59D","rank":"normal"}],"P26":[{"mainsnak":{"snaktype":"value","property":"P26","hash":"2aad2b9ad18df962d240b1892ef983c9cf9323fd","datavalue":{"value":"60","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$428E6390-EB5E-41EC-B273-B0FB25C2E97C","rank":"normal"}],"P25":[{"mainsnak":{"snaktype":"value","property":"P25","hash":"44b81cbbf6b2d038b4b7d86684a071cf08ad7770","datavalue":{"value":"3","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$3A536A79-A488-4919-9F95-DBDCAC07EF09","rank":"normal"}],"P128":[{"mainsnak":{"snaktype":"value","property":"P128","hash":"d952b04c8b58778be69ad24c7a86c2c4c4a83018","datavalue":{"value":"273-279","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$2B098DE7-0587-4848-A0F4-98962A6F5D8C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1b938c134f917cd65235780323a1bee69ad2a3c","datavalue":{"value":{"time":"+1992-08-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":10,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q139206$F3FCED17-FF28-4B9D-8269-CAA34C0B20CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q139206$79BAC093-FA68-4A51-B993-439EF2828CC5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"832387d421a802acc0f22447282f2ce367f3b207","datavalue":{"value":{"entity-type":"item","numeric-id":139204,"id":"Q139204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$50AF8905-78DF-4B15-BA29-C6E442539393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"88a0f9d8352da64441174f974f603163ab9e7235","datavalue":{"value":{"entity-type":"item","numeric-id":139205,"id":"Q139205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$3A885F90-1962-44E4-84F9-57AA52B1517D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"058e02b14f73fa961e8230ed8e0d6de6f8c67a8b","datavalue":{"value":{"entity-type":"item","numeric-id":262242,"id":"Q262242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$A96706AE-7ECB-4BAF-9FA8-4335B2D06D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"689f0097808e0ebdfd3bc5250e1c6d60df9ca6cc","datavalue":{"value":{"entity-type":"item","numeric-id":1278721,"id":"Q1278721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$CC9DDFC9-CDDD-491C-BC62-C2C9BDEF0D48","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"caf77d1497baecfbd42dcead1f92b628acadeac2","datavalue":{"value":{"text":"Approximation algorithms for three-dimensional assignment problems with triangle inequalities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q139206$D9977D71-2733-49F3-B420-F54F10BFE372","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"20086139932b69b2c8f622c8221498eb07a4baf6","datavalue":{"value":"0761.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$0685E7A5-DF79-4708-A9F1-886A44E59DD6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f62eca8ad41bbd04814dca50745888b898b95fe5","datavalue":{"value":"The three-dimensional assignment problem (3DA) is defined as follows. Given are three disjoint \\(n\\)-sets of points, and nonnegative costs associated with each triangle consisting of exactly one point from each set. The problem is to find a minimum-weight collection of a triangles covering each point exactly once. We consider the special cases of 3DA where a distance (verifying the triangle inequalities) is defined on the set of points, and the cost of a triangle is either the sum of the lengths of its sides (problem \\(T\\Delta\\)) or the sum of the lengths of its two shortest sides (problem \\(S\\Delta\\)). We prove that \\(T\\Delta\\) and \\(S\\Delta\\) are NP-hard. For both \\(T\\Delta\\) and \\(S\\Delta\\), we present 1/2- and 1/3-approximate algorithms, i.e. heuristics which always deliver a feasible solution whose cost is at most 3/2, resp. 4/3, of the optimal cost. Computational experiments indicate that the performance of these heuristics is excellent on randomly generated instances of \\(T\\Delta\\) and \\(S\\Delta\\).   Extensions of the previous results to the \\(k\\)-dimensional case \\((k\\geq 3)\\) were obtained by \\textit{H.-J. Bandelt, Y. Crama} and \\textit{F. C. Spieksma}, ``Approximation algorithms for multidimensional assignment problems with decomposable costs'' [to appear in Discrete Appl. Math.].","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$5843394C-C69D-44CB-ADF7-8905C91AD551","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$ACD17A72-6DFE-4039-932D-6A9F188807FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$03A66F19-03C2-4F9D-9777-A0CC8E81D8D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$E6965079-F5BD-4876-BCA8-17801485C102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$F00C7852-2F81-4A44-A0D8-34CA628E4F6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e50a6470f85c9b5aebdfef3cc6f67c9e97096378","datavalue":{"value":"94374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$BC96F4E6-3D61-41D5-B73D-77A4C2A1CD9D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2804b89ea3fc8440c6458d93b006da8f69b7ecfe","datavalue":{"value":"computational analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$9D6B6EC7-82C8-4AC7-B9C8-1A3A0B87BCAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a408d882c21002e385fa2d7522f3707d66188117","datavalue":{"value":"three-dimensional assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$CC276FC6-10E6-4BAA-9ED3-31C9A7C95D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q139206$692E9109-D9C2-4C40-85B3-B2B897E9D83B","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":"Q139206$7DFFB6D9-62E9-4F0B-AE02-F699A027B4E5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3303e5a25ab003c002f1c7deef3b1ec30778547c","datavalue":{"value":{"entity-type":"item","numeric-id":2276881,"id":"Q2276881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$8FA4A5D5-6FE3-4057-8EC3-E9B15383E35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc6488adbf9450db9ede8beb7e35200ade9dc417","datavalue":{"value":{"entity-type":"item","numeric-id":922276,"id":"Q922276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$556286A6-6B26-4E3C-A8CF-6F8F2BBCF7AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8be57b49e14a6f9de1043b8a908e157f2f01061","datavalue":{"value":{"entity-type":"item","numeric-id":4050393,"id":"Q4050393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$76DEA21E-0905-4102-A394-F121C35F4315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b197aa69a6de8e380409a00c02f183f164b6834","datavalue":{"value":{"entity-type":"item","numeric-id":3916373,"id":"Q3916373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$6865D085-9A5F-462D-9113-04D138DDF95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$AC349BF1-82AB-421F-ACBE-E7C90F1460A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6afe46348e014744711f326af9627976e19d5a6","datavalue":{"value":{"entity-type":"item","numeric-id":4065285,"id":"Q4065285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$0A5F305A-AEF9-4202-91A7-CFF7D5FB516C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q139206$CDE840C6-1653-4B2A-8429-E8E24F238C6F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aafd3dbafdbfc4c272d0d68cb901dfdd6fe1c093","datavalue":{"value":"https://doi.org/10.1016/0377-2217(92)90078-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q139206$26E35B9A-FA28-4165-B29F-BC45DEDB11AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4fc08c6ba9dd0555cbc3bf14eaf7bf2287962752","datavalue":{"value":"W2065841482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$B514B978-1053-4898-BC10-E6D009C8A999","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a26ab04a6b2b9529175ca8384fb84606e3fbb24","datavalue":{"value":"10.1016/0377-2217(92)90078-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q139206$2B516363-3C7A-4F98-8F5A-8991F1A71BF0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71729eff0ad8af06276f3340f2a64b7606d2523a","datavalue":{"value":{"entity-type":"item","numeric-id":1327216,"id":"Q1327216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"812d2d3062b850b87a860ac6431d3e31c256f956","datavalue":{"value":{"amount":"+0.8363627791404724","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":"Q139206$ED006743-066F-4404-97D4-E72F5D0C0968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eb93b44a8533cd5ea1108a7fdb240988ce521da","datavalue":{"value":{"entity-type":"item","numeric-id":845547,"id":"Q845547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3715ceecff051b188fd41acfaf3bcd323ae01621","datavalue":{"value":{"amount":"+0.8362335562705994","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":"Q139206$360D5F5F-D835-4994-B11C-7B3718C4E66A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db70e249eda2c283d7f66604596e1888eb6debe8","datavalue":{"value":{"entity-type":"item","numeric-id":4209365,"id":"Q4209365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2498fd7efb75fa5151ee46b0a205c809acc56588","datavalue":{"value":{"amount":"+0.8359177112579346","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":"Q139206$062E9DFC-B0A4-43A0-B72B-313AC67B8AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b15e3648bb54b54658260c977075eb4ced76ea05","datavalue":{"value":{"entity-type":"item","numeric-id":1278259,"id":"Q1278259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21300b779e79764d4b89f722ea3e03b61d36422a","datavalue":{"value":{"amount":"+0.8205593228340149","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":"Q139206$20E1C80B-7A69-4A66-8676-3C2935D497AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1977dc970b0da5f20e70f9b5fa083a88abd421e5","datavalue":{"value":{"entity-type":"item","numeric-id":1751127,"id":"Q1751127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"071fedeedca62a5dc2152354b73c5858007aec9f","datavalue":{"value":{"amount":"+0.8150947690010071","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":"Q139206$568C1488-4864-4AEE-AD5B-F8B2E86EF03C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:139206","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:139206"}}}}}