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

DOI10.1007/BF02187869zbMath0621.90054MaRDI QIDQ1090604

Martin Kolinek

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131008

zbMATH Keywords

hyperplanescomputational geometrylinear decision treeaffine testslinear incidence geometryn-city Traveling Salesman Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Other problems of combinatorial convexity (52A37)

Cites Work

• A difference Picard theorem for meromorphic functions of several variables
• Proving simultaneous positivity of linear forms
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• On the Polyhedral Decision Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems