2 ms·
OK, I've really only skimmed it, but here's an impression ... He spends a huge amount of time setting up the very very specific equations, and then waves a mag
by ColinWright 14y ago
OK, I've really only skimmed it, but here's an impression ...
He spends a huge amount of time setting up the very very specific equations, and then waves a magic wand saying "This is a Linear Programming Problem which can be solved in polynomial time."
It looks to me like an integer linear programming problem, and that's known to be NP-Complete. There doesn't seem to be anywhere that he takes a non-integer solution and converts it in polynomial time to an integer solution (or provably fails), nor is there anywhere that shows how to find an integer solution in among all the possibly exponentially many solutions it might produce.
- danpalmer 14y agoNot sure if this helps, but this paper shows that Integer Linear Programming is solvable in 'pseudo polynomial time' when dealing with fixed constraints - http://lara.epfl.ch/web2010/_media/papadimitriou81complexityintegerprogramming.pdf http://lara.epfl.ch/web2010/_media/papadimitriou81complexity...
- ambrop7 14y agowhich essentially means it needs exponential time, and as such is useless
- nate_martin 14y agoAccording to wikipedia Integer Programming is NP-Hard http://en.wikipedia.org/wiki/Integer_programming http://en.wikipedia.org/wiki/Integer_programming
- danpalmer 14y agoAs far as I understand from the two papers, and I haven't finished reading them, nor do I expect to understand it all, but this appears to be very much an LP problem, not ILP, from what I've read so far.
- ColinWright 14y agoI don't have time now, and I'm unlikely to have time in the next six months, but it looks awfully like he's setting up a standard LP problem, but I don't see how he's extracting integer solutions from it. I expect there to be errors, and I expect them to be subtle, and I expect that if they're pointed out he'll push them around to some other place where they're hard to find. Having said that, I haven't read it thoroughly (and won't have the time to) and I'm disinclined to. Not that that's any great loss - I'm not an expert.