3 ms·
The greedy approach has an 1-1/e type of approximatation. You basically prove that the problem is in the class and then solve it greedily. It’s not much differe
by mirker 5y ago
The greedy approach has an 1-1/e type of approximatation. You basically prove that the problem is in the class and then solve it greedily. It’s not much different than proving the problem is convex and then using gradient descent.
- kragen 5y agoPeople mostly use gradient descent to "solve" nonconvex problems.
- mirker 5y agoThere isn’t much theory on why it works in the nonconvex case. You can similarly make discrete heuristic algorithms for sorting, etc. with no guarantees. Anyway, as nonconvex models are usually stacked convex models, you can find works that incorporate these submodular functions as neural network layers.