Comment

Comment by m3koval

Unfortunately not. Matrix inversion (or any type of linear algebra, really) deals with real numbers. This problem is nearly a linear program, which can be solved very efficiently, except that some variables are constrained to { 0, 1 }. As a result, it's an integer program, which is NP-hard. Intuitively, this is hard because there are no derivatives (e.g. gradient, Hessian) to exploit in discrete optimization problems.

One heuristic is to solve an IP is to relax the integer constraint to inequality constraints, solve the LP, and round the results. However, this can do arbitrarily poorly on most problems.

parent m3koval 13 years ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton