[macosxnerd101]

This link provides a neat LP formulation for the independent set problem. For those not familiar, linear programs (LPs) are optimization problems where the variables take values in the real numbers. We can efficiently solve LPs (LP is in the complexity class P). The INDEPENDENT SET problem is one of Karp's 21 NP-Complete problems.

The optimization problem presented for the INDEPENDENT SET problem is an integer program, where the variables are integers rather than continuous. The author relaxes the IP into an LP. It turns out that when the LP result is integral, we can determine the maximum independent set of the graph in polynomial time. It is interesting as well that variables only take on values in { 0, 1, 1/2 }, which provides some basis to guess and check for an independent set.

This is a neat read for those interested in graph theory, algorithms, complexity, or optimization. It's also a good example of where modeling a problem can be advantageous. As computer scientists, we often think about finding a solution rather than describing the problem. Mathematical optimization really forces us to describe the problem concisely.

http://yaroslavvb.bl...or-maximum.html

[ishkabible]

What kind of real numbers are used in LP? I ask because I'm pretty interested in exact real arithmetic. I wouldn't have expected exact real arithmetic to be used here however.

[macosxnerd101]

We generally assume each variable is in R. I'm not familiar with specifics on numerical techniques for computing LP solutions.

[ishkabible]

I guess I'm curious how do we know that it is solvable in polynomial time without specifying an algorithm to do it? That algorithm must either a) assume less than exact real number representation or b) make some sketchy assumptions about how efficient it is to perform operations on exact reals or c) ignored this issue. I'd be pretty disappointed if the issue was ignored but not surprised; people are REALLY loose with real numbers IMO and bothers the crap out of me.

This post has been edited by ishkabible: 12 July 2015 - 01:24 PM

[macosxnerd101]

The Ellipsoid algorithm solves LPs in polynomial time, providing an algorithm to show LINEAR PROGRAMMING is in the complexity class P. I'm not familiar with the specifics of Ellipsoid or the particular proof to show LP is in the class P.

[ishkabible]

It gives me something to go off of. I'll look at it and if I can wrap my head around it I'll report back.

edit:
It was well pointed out in the literature on the matter that this was not *really* solving general LP but was decidedly of practical interest. It explicitly makes use of the number of bits used in the representation of its "real numbers" so they didn't just brush the issue off.

edit2:
And confirmed. The general strategy for dealing with these kind of problems is to assume that you can perform operations real-valued operations exactly (even non-computable ones) and then account for lack of precession later. So it is a very strange abstract machine they use to prove that LP is P-complete; namely one that can compare real numbers as if it has an oracle and can efficiently perform exact real arithmetic. I think if one is not carful with these sort of machines you could solve the halting problem so you have to make sure you are sticking to the spirt of the problem here and not doing something crazy when making these sorts of assumptions.

source

This is basically what I was afraid of. This research isn't bad as long as you don't do tricky things with equality but I HATE the thought of operating in a sketchy system like this.

This post has been edited by ishkabible: 12 July 2015 - 05:18 PM

[Skydiver]

My father is a big LP fan.A long time ago, I asked him about LP and if it was good for making sets of binary decisions. He always used to say "use the right tool for the job", and said that unless there costs could be associated with the decisions, it would tend to be difficult even with integer LP. It would probably be easier to use a different algorithm. I'm quite sure that he'll get a kick out of the results from the original post.