1
$\begingroup$

Is there a site that keeps track of the "current best algorithms", e.g., for certain combinatorial optimization problems?

In the latter there exists a range of classic problems such as MIN st-CUT or MAX FLOW, for which the best algorithms seem to be somewhat hidden in the literature.

$\endgroup$
  • 1
    $\begingroup$ Wikipedia, to some extent. $\endgroup$ – Yuval Filmus Sep 4 at 11:04
1
$\begingroup$

"Best algorithm" is a fuzzy term. The algorithm which is best for some particular case can very well be absolutely worst for another, similar problem. Problems differ in details (and not-so-details), in size, in available resources, sometimes an exact solution is essential, other times a rough approximation is good enough. And there are literally thousands of algorithms, with new ones added each day.

$\endgroup$
  • $\begingroup$ Most certainly. But I believe there are plenty of problems for which there in fact is a very clear "progress bar". Matrix multiplication is one such example. For the examples mentioned in the original question, a clearly defined setting would be "sequential algorithms for epsilon-approximation". $\endgroup$ – smapers Sep 5 at 13:43
  • 1
    $\begingroup$ @smapers "Matrix multiplication is one such example." Is it? You can measure progress on $\omega$ (in $O(n^\omega)$), but many improvements on that front have too large constants in front of the polynomial to be practical. This is why Beniamini and Schwartz argue to also look at the leading coefficient. So, which algorithm is better? One with a larger leading coefficient and smaller exponent or vice versa? I'd say this will depend on $n$, i.e. on you input instance. $\endgroup$ – Discrete lizard Sep 5 at 13:55
  • $\begingroup$ Ok, maybe I should have posted my question on the "theoretical CS" site ;) $\endgroup$ – smapers Sep 5 at 13:56
  • 1
    $\begingroup$ For most problems, there in fact isn't a very clear "progress bar". The easy solutions have been found. What remains is often very specific, and "bestness" subjective. $\endgroup$ – Yves Daoust Sep 5 at 15:44

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.