|
|
|
|
|
|
by LegionMammal978
435 days ago
|
|
|
Yeah, perhaps I was a bit unfair, it's just that the problems that have gotten good results never seem to be the ones I need! C'est la vie, I suppose. (In particular, I've been working with recognizing small formal languages from samples, which has usually NP-hard, but has a surprising number of solvable cases. But my impression is that most modern work has gone into various forms of probabilistic grammars, which aren't really what I'm looking for.) Sometimes it's also helpful to look into approximation algorithms, e.g., a good LLL implementation can work wonders for certain problems. But heaven forbid someone obtains an inapproximability result for your problem, then you're really in trouble. |
|
|
This is not (necessarily) true:
For example, there exists a great approximation algorithm (Goemans-Williamson algorithm) for MAXCUT in graphs with non-negative edge weights.
On the other hand, when negative weights do occur, one can show (unless P=NP) that there exists no polynomial-time approximation algorithm for which the approximation guarantee is a constant factor times the optimal solution.
But since the Goemans-Williamson algorithm is a great algorithm (if the Unique Games Conjecture holds, and P != NP, it has the best approximation guarantee that any approximation algorithm for MAXCUT with non-negative weights can get in polynomial time) nobody "forbids" you to use it in situations where also negative edge weights can occur. You will loose the approximation goodness guarentee, but in practice, this algorithm nevertheless gives good results in this situation, just not certified good results.