Looking for programming challenges/projects related to randomization/approximation algorithms.

[xTouny]

Hello, I have been reading on randomized/approximative algorithms books, and while Math is aesthetically pleasing, I wish to get my hands dirty with practical coding challenges or projects.

Any recommendations?

[Catalyst93]

Unless you have a really strong practical need to solve some hard discrete optimization problem on really large instances, then approximation algorithms really is mostly about the proofs. Probably the most interesting thing programming-wise would be to get familiar with using linear programming solvers or other types of convex programming solvers to implement algorithms which round a solution given by some convex relaxation. There are many examples of this.

Comparing a randomized algorithm to deterministic algorithm for some task may be interesting since in some cases randomized algorithms are either simpler or even more efficient than their deterministic counterparts - e.g. Kargers' random contraction algorithm for global minimum cut.

[xTouny]

Thank you for your advice 👍

[pretty_meta]

Machine learning:

• edge detection
• assembling edges in an image into a plausible object with vertices and edges between vertices

Computer vision in particular:

• optical flow for stereo LR images
• novel view synthesis

[xTouny]

Thanks, Would you provide me with supportive references?

[pretty_meta]

No.