Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2006
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/cs/0611008 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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(n^9)) 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.