Hacker News Reader

Example: You want to bisect the nodes of an edge-weighted graph into two sets of equal size such that the sum of the edge weights between the two parts is maximized.

The best approximation algorithm (it's NP-hard) runs in time O(n^(10^100)):

https://arxiv.org/pdf/1205.0458v2.pdf

For more examples see here http://cstheory.stackexchange.com/questions/6660/polynomial-...

View on HN

It's interesting though that the examples you provided are all approximations for known NP-hard problems, and in many cases the free parameter that lets you get arbitrarily large constants depends on how close to optimal you want the approximation to be.

Do you have examples of large-constant algorithms in P that are not approximations of NP-Hard problems?

Not quite the same as the earlier conversation on exponents, but since you mentioned constants, matrix multiplication is a prime example -- apparently Coppersmith-Winograd has enormous constants ("only provides an advantage for matrices so large that they cannot be processed by modern hardware") that I can't find them (the wiki article doesn't really have a proper source, and preliminary searching also yielded no concrete results -- possibly because the proof of existence was non-constructive?).

Reply on news.ycombinator.com