undefined | Better HN

0 pointsfoota2y ago0 comments

Maybe the answer then is to find what these hard cases are and use them in heuristics or approximate algorithms? If we could tell when part of the problem is hard, and maybe bound the error for them, and use an exact algorithm for other parts of the problem, you could get a better result in most cases without it blowing up on you.

0 comments

kaba02y ago

Well, you can just start an exact solver on the problem in one thread, and an approximate algorithm on another. If the former doesn’t finish in n seconds, you cancel it and use the result of the latter.

footaOP2y ago

The advantage of combining them though is that you might be able to treat different subparts of the problem differently (which is the hard part), so that you could use an approximate algorithm for the hard part of it, and an exact algorithm for the easy part.

Thi of course assumes the problem can be divided in this way, which is fairly speculative.

j / k navigate · click thread line to collapse

0 comments

kaba02y ago

footaOP2y ago

Thi of course assumes the problem can be divided in this way, which is fairly speculative.

j / k navigate · click thread line to collapse