{"entities":{"Q1090604":{"pageid":1101356,"ns":120,"title":"Item:Q1090604","lastrevid":66430146,"modified":"2026-04-12T10:02:06Z","type":"item","id":"Q1090604","labels":{"en":{"language":"en","value":"A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4008101"}},"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":"Q1090604$EA83B804-48B8-4007-9223-43E0FA86D538","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7a9eefeeec12cd82bd87be3d9e9ce993cdfbe58e","datavalue":{"value":{"text":"A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090604$D40E0485-1E4B-478C-9369-E56C27791707","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"20cd6263c838aff9c52dc6dffa38f21857ede031","datavalue":{"value":"0621.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090604$B953B497-3224-446D-BAFE-4E2E1522744D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c01a9e429a971c888d09312cbcb20a9c45d30f98","datavalue":{"value":"10.1007/BF02187869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090604$1412B2BC-1030-421F-BBB3-5165B4331283","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a7a721850babc56726f4c2cc95361a798300ce4","datavalue":{"value":{"entity-type":"item","numeric-id":1090603,"id":"Q1090603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$0EAD0EFA-8A72-4F9D-B292-93A7A3CFE118","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$593CC110-8048-4756-99DA-8675FE3B87EB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1090604$819C3130-3AB7-40CD-9593-DD42CD0D0B0E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f218692fb003f3a9cf94b478346df359a31c75f3","datavalue":{"value":"https://eudml.org/doc/131008","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090604$89AC6DF8-216D-4562-A9BC-C57F0810EB6A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a239a5e78f42a9afc85c9471033e6c72ed36a0bb","datavalue":{"value":"This paper extends results obtained by F. Meyer auf der Heide and Rabin. The main theorem is as follows: Let \\(S=\\{H_ 1,...,H_ k\\}\\) be a nonempty set of hyperplanes in \\({\\mathbb{R}}^ d\\). Assume \\(H_ i\\) has equation \\(\\sum^{d}_{j=1}a_{ij}x_ j+a_{i(d+1)}=0\\) where the \\(a_{ij}'s\\) are integer and the \\(x_ j's\\) are Cartesian coordinates in \\({\\mathbb{R}}^ d\\). Then there is a linear decision tree performing affine tests of the form \\(''\\sum^{d}_{j=1}b_ jx_ j+b_{d+1}\\lesseqgtr 0?''\\) which determines the position of an input \\(x\\in {\\mathbb{R}}^ d\\) with respect to all hyperplanes in S in time at most \\(2d^ 4\\log_ 2d+2d^ 4\\log_ 2M(S)+O(d^ 3)\\) where \\(M(S)=\\max \\{| a_{ij}|:\\) \\(1\\leq i\\leq k\\), \\(1\\leq j\\leq d+1\\}\\). As an example the n-city Traveling Salesman Problem in the linear decision tree model of computation can be solved in time \\(4n^ 8\\log_ 2n+O(n^ 6)\\). Many integer programming problems can be treated in a similar way.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$CF59C293-BACB-41F9-BFC6-156DAD962CCF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090604$052A49DD-B943-46D0-A064-481EC88230FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090604$6BF81817-8CEF-4F36-B354-58AE1689482F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090604$94D8DCD5-CBB6-487A-A3DC-3DAD79D32D48","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"179d7f623cdb6680d1ab980453e7cfb6c4ffad55","datavalue":{"value":"4008101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090604$51FDC6E6-6B00-4FBC-82F5-853BCFEE884C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c17f6d0e44682292037a882474844b9c13dd4c75","datavalue":{"value":"linear incidence geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$E6C37F13-6850-4050-8BD4-3E5921B86F45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$6204C202-B57A-4487-81B9-6C2E5B56FB0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2ed70d6d877ff1b2606a4f9167da52c165cc3a6","datavalue":{"value":"hyperplanes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$6A85B44F-6056-4579-8051-8459869E2834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d93f577134a0d0dc4711e2f6414347a71d32c769","datavalue":{"value":"linear decision tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$80AFFFD5-AA36-4B64-8735-7934D1ACE088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bddddd73a229ffa55655005d5802320a212f910","datavalue":{"value":"affine tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$4C439191-4E0C-4F6E-ADB0-1447369B5943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c39e9f82ae3f639f5ef879e7dcc1393c5fe03be6","datavalue":{"value":"n-city Traveling Salesman Problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090604$6669D461-EB1D-4E15-BAB0-AE9FEF457652","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$6535D711-52C7-433F-B5CF-9D61CC192D30","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":"Q1090604$D5723EB0-9FDD-4233-ACF9-C62576EC4B60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad01755951c5d7c4169b71e6540d5e447e759957","datavalue":{"value":{"entity-type":"item","numeric-id":428965,"id":"Q428965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$B5A74375-CDCE-4747-A938-B8AAD37A0AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd9e232f68336d7ae8cf0bc4c0bb8edd61f7b5e8","datavalue":{"value":{"entity-type":"item","numeric-id":4134963,"id":"Q4134963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$E8159C51-AE14-4E80-9BFD-96A5EC529067","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":"Q1090604$42CB1C96-9591-4AD3-B3E5-82D9EFB44D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8fea9a5dba7c0c825c98a79aa7f9c13491987b","datavalue":{"value":{"entity-type":"item","numeric-id":5547252,"id":"Q5547252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$2623C070-5977-4F06-B82F-ED1BD7332367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74562e1bfcbeccc3b58591b3fa2554f211008cea","datavalue":{"value":{"entity-type":"item","numeric-id":3768396,"id":"Q3768396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$A415D234-99CC-4755-862B-C9777A07767D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb19f12b7c7c70b4050c076bf47c50f4b7b37bb1","datavalue":{"value":{"entity-type":"item","numeric-id":2265260,"id":"Q2265260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$C3956DF1-C6B4-4D94-99B6-E8D7304EBCEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a23c2117b50f0af001c9d12f9656380de315a6c","datavalue":{"value":{"entity-type":"item","numeric-id":5805005,"id":"Q5805005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$DCE70A66-FF35-4787-8DC4-D00A6FFA1986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96337ff7de70ff83a8e40c9366e39307f913514e","datavalue":{"value":{"entity-type":"item","numeric-id":5762592,"id":"Q5762592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$9EC5B058-B359-4399-9102-EB91F313E449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf851580ae91acae3bb4962517461ba598b1a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":3893331,"id":"Q3893331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090604$449635A5-F6B5-4A97-958F-490644B70F25","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8c5cdbda0208e9453f45ed7f712f51dd01b29b7","datavalue":{"value":{"entity-type":"item","numeric-id":4382797,"id":"Q4382797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37241025d7efd30254bfbd11a0a06d409bad3054","datavalue":{"value":{"amount":"+0.90165234","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$72DE2EBB-3F3A-4BDE-99DD-E60DF27DF431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65270f76caab8780048904b1cc66514612d450a7","datavalue":{"value":{"entity-type":"item","numeric-id":5359124,"id":"Q5359124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4a28d5d4e0b1c43ff3a76b00672db2b69f232fd","datavalue":{"value":{"amount":"+0.8791443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$7AC0852D-23D9-44AA-BC6B-F7C7A0171F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d343ce0bef5a9c20b51a13e69cc260bdfb874333","datavalue":{"value":{"entity-type":"item","numeric-id":3587419,"id":"Q3587419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccfb3b1ee5000aeff192f26590815e986fffbb16","datavalue":{"value":{"amount":"+0.8791442","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$154F5786-E177-481F-9E38-BE75764673D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd76e43185efebf5ae1bdf77f9c8f77fde3c9a90","datavalue":{"value":{"entity-type":"item","numeric-id":3328253,"id":"Q3328253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf989361630db367d08564dc729a51606183f454","datavalue":{"value":{"amount":"+0.8764862","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$AF5F387F-55F6-40C0-9FD5-32FCBCB132BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"048c428e820c5898cfd443eeb1329e08424eb796","datavalue":{"value":{"entity-type":"item","numeric-id":5753758,"id":"Q5753758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"158a726e8ad4ba5bb85e50b9085f6fcfb73317e8","datavalue":{"value":{"amount":"+0.8683562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$77B30495-8FEB-4E79-A7A5-7DB846A50A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08b19681cf0da7b49d9c06835c5b2f18732981f5","datavalue":{"value":{"entity-type":"item","numeric-id":3351148,"id":"Q3351148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8800792114ca1e9670eec8cea9baa890fb333f34","datavalue":{"value":{"amount":"+0.8662092","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$7DA41D85-4AD3-42AF-A51B-7E770E8E2652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd51965d610f9fd2a052eb10f89111fa8f221822","datavalue":{"value":{"entity-type":"item","numeric-id":2748381,"id":"Q2748381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8ef876983a223b23231d813e89134c57fefa542","datavalue":{"value":{"amount":"+0.86447626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$A665C5AB-FF0A-4009-BEDF-F7D2096E2511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e16b45298d3581b8df2ddc3aacd780b55939d1","datavalue":{"value":{"entity-type":"item","numeric-id":4645944,"id":"Q4645944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7422e252e1f17cd5c2bf64058496dfc32663e6d","datavalue":{"value":{"amount":"+0.86384875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$A7FF1FF1-3705-4C79-A4D1-97272BD00D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"827339e7ddf1f10feb24fbe60d0d3cc8b4ec97b1","datavalue":{"value":{"entity-type":"item","numeric-id":4645932,"id":"Q4645932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffa308d409894bea8f3ab0dbe84f2d0caaf7e7b4","datavalue":{"value":{"amount":"+0.86205876","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$011627BF-4C05-46FF-853B-F2B3F1D72F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a28e53d761f5df2e27d14c987f81a003340d3feb","datavalue":{"value":{"entity-type":"item","numeric-id":4016908,"id":"Q4016908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e534343442b88a94a97ee31bb8b08bb826ea8364","datavalue":{"value":{"amount":"+0.8595514","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090604$26C4C9D2-D448-43B5-9163-23AA8CABC290","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial-time_linear_decision_tree_for_the_traveling_salesman_problem_and_other_NP-complete_problems"}}}}}