{"entities":{"Q2375707":{"pageid":2386450,"ns":120,"title":"Item:Q2375707","lastrevid":56784204,"modified":"2026-03-23T14:26:31Z","type":"item","id":"Q2375707","labels":{"en":{"language":"en","value":"An improved exact algorithm for least-squares unidimensional scaling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6175972"}},"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":"Q2375707$E2D50869-2DE8-40CD-95DB-772C044B1489","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"559161a12b8605c23cad17d1cc11fdde4dba3a5b","datavalue":{"value":{"text":"An improved exact algorithm for least-squares unidimensional scaling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2375707$C9434598-EAEA-4929-A99A-4CA87F24A7A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c975f5bf9c37b91d642691a3deb5c0e715c618e","datavalue":{"value":"1266.65072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$4D297A24-5AC0-41EF-B9D6-67A3F15B83FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1991dcbbdd8c4ec54472fe360fd5c2462e3504fe","datavalue":{"value":"10.1155/2013/890589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$8E01980D-7002-4233-B1AD-75DD12B13A44","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$61D96EDC-847C-4CEA-BA8D-D09AD5EDCBF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b84d2a34981f1c1a0d0fb543ea5aabc14a21194b","datavalue":{"value":{"time":"+2013-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2375707$DB83AB40-1516-495D-9072-7608A51766A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65b55e041728e82d3c34fe90eeb49d46a34aa987","datavalue":{"value":"Summary: Given \\(n\\) objects and an \\(n \\times n\\) symmetric dissimilarity matrix \\(D\\) with zero main diagonal and nonnegative off-diagonal entries, the least-squares unidimensional scaling problem asks to find an arrangement of objects along a straight line such that the pairwise distances between them reflect dissimilarities represented by the matrix \\(D\\). In this paper, we propose an improved branch-and-bound algorithm for solving this problem. The main ingredients of the algorithm include an innovative upper bounding technique relying on the linear assignment model and a dominance test which allows considerably reducing the redundancy in the enumeration process. An initial lower bound for the algorithm is provided by an iterated tabu search heuristic. To enhance the performance of this heuristic we develop an efficient method for exploring the pairwise interchange neighborhood of a solution in the search space. The basic principle and formulas of the method are also used in the implementation of the dominance test. We report computational results for both randomly generated and real-life based problem instances. In particular, we were able to solve to guaranteed optimality the problem defined by a \\(36 \\times 36\\) Morse code dissimilarity matrix.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2375707$CE841666-A0FA-4D04-A0FF-1971B0D5B603","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"01c01fe808ed718e2875de738d94f61942d3944d","datavalue":{"value":"65F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$B9C3FB32-9C9E-4F4F-9E40-491A4DA8DB77","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2714cc711a90e11eeaa7911ccff7bb998f99186c","datavalue":{"value":"6175972","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$3FB496CD-3DDB-4C57-9530-A6FF51B72666","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1e12c90047e61e815be7ffbb711746350ed1badf","datavalue":{"value":"Q59005050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$F0854B01-A440-4553-848A-DC4585A7301A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6d4c4ee662a66037f9db99ed3a9226399541c9b","datavalue":{"value":{"entity-type":"item","numeric-id":319871,"id":"Q319871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$BA63524F-1B7D-4F74-BA0C-83E1D6B517E9","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7f251f3cc445b4bb157aac16ee1a1507bb821b0a","datavalue":{"value":{"entity-type":"item","numeric-id":27331,"id":"Q27331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$70864FBF-536C-4715-A3DD-6EB933BA0CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"56d3d98c4928b64e07cbfdf7c73b067f9535e2e7","datavalue":{"value":{"entity-type":"item","numeric-id":33871,"id":"Q33871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$CC886833-1466-42D7-A48D-2A34EFD40621","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":"Q2375707$DC4311FB-E885-4118-8552-7D709DDA5E2F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6825622ff0c4b375b3779687988273a767016a93","datavalue":{"value":"https://doi.org/10.1155/2013/890589","type":"string"},"datatype":"url"},"type":"statement","id":"Q2375707$1BE2BAAC-7F2C-4458-9964-574C384F5EF6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e56dba6b2e800402184196b46be27b4ed4130292","datavalue":{"value":"W1978677945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$812ED08E-DF78-4024-9ED7-EF776762D2B1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b3d70e0e082c8adac8e6925c849b8ad33cf612","datavalue":{"value":{"entity-type":"item","numeric-id":2569880,"id":"Q2569880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$1BC256A3-A9AD-4081-9A23-FED78AF7526E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8458623f44197e8370947ef79913b533a36800ed","datavalue":{"value":{"entity-type":"item","numeric-id":879809,"id":"Q879809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$93FE81B2-735D-4C8F-99E4-139187F7FEF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9fa76d6641fa09d94cb95d7dbc733fafddd671b","datavalue":{"value":{"entity-type":"item","numeric-id":976388,"id":"Q976388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$230ED7D4-B7C1-4E88-A1D5-A294A3B69222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ee0ae085b9f196259fc5b1a2f0d4fe693ef875f","datavalue":{"value":{"entity-type":"item","numeric-id":2804733,"id":"Q2804733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$A8A48A64-3AA4-4A1B-AEFF-D4E32869A092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06f0a1934d9f6d2dd72636094145d9e84a1a7ce8","datavalue":{"value":{"entity-type":"item","numeric-id":2260052,"id":"Q2260052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$11A74543-2B9C-49E0-9837-66F132ECF9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9dfd9a011741601abb089649f66b1e8d10f6cee","datavalue":{"value":{"entity-type":"item","numeric-id":1566088,"id":"Q1566088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$C4903E80-73FA-4959-AE31-A934051EE4F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a60e6221ef83d49a743481b246e7bc03d57c73a","datavalue":{"value":{"entity-type":"item","numeric-id":5706832,"id":"Q5706832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$CA005F97-CCBC-42A1-BA8B-FE40416BA82C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fef7baa15d59e323d6b20a84e8fbe9d00f9da06","datavalue":{"value":{"entity-type":"item","numeric-id":2563531,"id":"Q2563531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$9CFBA4A1-C649-41C0-81F7-82D05B5791C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b93aec7469d167c9de69359476f9c24ac6103e98","datavalue":{"value":{"entity-type":"item","numeric-id":818992,"id":"Q818992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$BCE1AAF2-EA91-4407-8B9F-5313239FDCE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bccda80072ef22cd0ff66e2e04e87cb0ce3ce25f","datavalue":{"value":{"entity-type":"item","numeric-id":265251,"id":"Q265251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$BACFC29F-C36D-4A6A-8114-D3D27BDB37A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5db0cc086c17b995a82914a7341ebdd7a4971ca","datavalue":{"value":{"entity-type":"item","numeric-id":477965,"id":"Q477965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$16A78C7B-7BD9-4718-80BB-8EBD590BD565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ad1a47164deb3622cb0b530cbfee4eba10f69e","datavalue":{"value":{"entity-type":"item","numeric-id":2381330,"id":"Q2381330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$736C5689-CD1B-471E-809A-6C3508A843ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8f25d0c15001860982d57df99c37ba699564fe9","datavalue":{"value":{"entity-type":"item","numeric-id":734870,"id":"Q734870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$E499C4E4-D366-4DCB-AD43-476306119B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9ebe120338a5fedc65ee7188b509d3bec21ef31","datavalue":{"value":{"entity-type":"item","numeric-id":411085,"id":"Q411085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$F4C7B9C2-3DB4-479C-98DF-DF5C2A102820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93a88f1aa332200c0659d5d170b03a4bbc410d30","datavalue":{"value":{"entity-type":"item","numeric-id":1760596,"id":"Q1760596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$46DBF0A6-CF06-45D8-971D-B45DAE291BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5013ff19f91b84740428256b58b8c7e26e9f25","datavalue":{"value":{"entity-type":"item","numeric-id":421551,"id":"Q421551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$3249AB95-12A1-41B1-8A91-D2F0174A65AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfc155cc261f7bea84b738cfac11dcdc9c890c34","datavalue":{"value":{"entity-type":"item","numeric-id":676477,"id":"Q676477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$5013584D-1DB5-4143-B1BD-29F1F3E9D9A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a86d62227bc18337e5d84d631c65ab1cc677a81","datavalue":{"value":{"entity-type":"item","numeric-id":2723176,"id":"Q2723176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$1797860D-EE84-4E8D-9916-878EE0CAB501","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"305bec476ee0b017ad77bd39c1b8a4e7072c1da9","datavalue":{"value":"journals/jam/Palubeckis13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2375707$C887983B-92B6-49A1-AF04-EBE70A4B2930","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9312969291651691481e5382b79d9ded35cc029d","datavalue":{"value":{"entity-type":"item","numeric-id":2260052,"id":"Q2260052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7f9bff76e961122577b79cd8b8ab75736e7d121","datavalue":{"value":{"amount":"+0.8649048805236816","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":"Q2375707$01DEA09F-D3DC-4D3D-8BE5-BE0F3B706A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c739e2c9d7c2fe29ac5569b37946589bcbd56734","datavalue":{"value":{"entity-type":"item","numeric-id":818992,"id":"Q818992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f0322f0f503302067efba67eef1d4ef432c68dc","datavalue":{"value":{"amount":"+0.8316648006439209","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":"Q2375707$E0165C93-6459-4CF8-89BA-6824A8E87390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8292b5f416850282e052ed83789f3406075977ac","datavalue":{"value":{"entity-type":"item","numeric-id":2563531,"id":"Q2563531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"050da8e2f601d0cd82a1e092273d15e1af831c3d","datavalue":{"value":{"amount":"+0.758402943611145","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":"Q2375707$82B04B2A-CADB-470E-B4C5-1F4B5B3C89C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf96d31d2aa9efb49af14ac725e7f0543575a4b3","datavalue":{"value":{"entity-type":"item","numeric-id":1393049,"id":"Q1393049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"874239c9ffad6b1f4cb9db400194b22f037433ef","datavalue":{"value":{"amount":"+0.7566322088241577","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":"Q2375707$0CD1AE2B-2D73-4285-82D2-DAAC8B5E5A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"881667fc817ed852e62b322a5ad0a43d28eceed9","datavalue":{"value":{"entity-type":"item","numeric-id":1029698,"id":"Q1029698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6882f21afaca13a9f2bbff525e089b10200b0b7b","datavalue":{"value":{"amount":"+0.745660126209259","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":"Q2375707$79F7B8DB-6883-411F-8E2D-62FAC5CEFD07","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2375707$694C9043-4824-4774-A7D4-AF8182A4B61A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2375707","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2375707"}}}}}