2
$\begingroup$

I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction.

I have came across the Min-Conflicts Algorithm which proved to be rather efficient in the context of the problem.

However, I have recently chanced upon the Coordinate Descent Algorithm and how strikingly it resembles the Min-Conflicts Algorithm.

Probably the only difference is that in Min-Conflicts, a random variable is selected to be modified at each step whereas Coordinate Descent cycles through the variables.

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent? If so why are classified differently?

$\endgroup$
0
$\begingroup$

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent?

In the same sense that A* and BFS are essentially equivalent except for the choice of which node to visit next, yes.

If so why are classified differently?

There are some problems for which Min-Conflicts performs asymptotically faster (in the expected-time sense) than Coordinate Descent, and vice versa. Ditto, there are some problems where one (generally) converges and the other (generally) doesn't.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.