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.

  • 2
    $\begingroup$ Recently such algorithms have been suggested for edit distance. $\endgroup$ – Yuval Filmus Nov 15 '19 at 10:05
  • $\begingroup$ I believe that people who works in designing efficient algorithm for some problems, they wanted sometimes linear time algorithms instead of quadratic or cubic or any other polynomial time algorithm, but it turns out that this is a very difficult approach. So, they turn to design an approximation/randomized (or both) algorithm with sublinear running time. See this survey about approximation algorithm with sublinear time by Czumaj and Sohler: "wisdom.weizmann.ac.il/~oded/PTW/sublin.pdf". $\endgroup$ – YOUSEFY Nov 16 '19 at 16:58
  • 1
    $\begingroup$ See also this video which is titled "Sublinear-time Approximation Algorithms" by Czumaj: youtube.com/watch?v=0wH2IiUa4hQ $\endgroup$ – YOUSEFY Nov 16 '19 at 17:00
  • $\begingroup$ You can check literature for such algorithms for matching-related problems. (e.g maximum cardinality matching, weighted) etc... $\endgroup$ – jjohn Nov 16 '19 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.