As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra activity to learn an approximate algorithm for a
P problem. I searched a lot on google but all I found were approximations for NP problems.
I was wondering if anybody can help and tell me a approximate algorithm for a problem with already a exact polynomial algorithm?
It will be very much better if the algorithm be a short and easy one.