2006/11/02 by Radosław Hofman, Hofman, Radoslaw
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.cs/0611008
This article discusses ability of Linear Programming models to be used as solvers of NP-complete problems. Integer Linear Programming is known as NP-complete problem, but non-integer Linear Programming problems can be solved in polynomial time, what places them in P class. During past three years there appeared some articles using LP to solve NP-complete problems. This methods use large number of variables (O(n9)) solving correctly almost all instances that can be solved in reasonable time. Can they solve infinitively large instances? This article gives answer to this question.