A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems (Q1090604)

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.