Categories
  • Computational complexity theory
  • Optimization algorithms and methods
    •   Encyclosphere.org ENCYCLOREADER
      supported by EncyclosphereKSF

    Exact algorithm

    From Handwiki - Reading time: 1 min

    In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality. Unless P = NP, an exact algorithm for an NP-hard optimization problem cannot run in worst-case polynomial time. There has been extensive research on finding exact algorithms whose running time is exponential with a low base.[1] [2]

    See also

    • Approximation-preserving reduction
    • APX is the class of problems with some constant-factor approximation algorithm
    • Heuristic algorithm
    • PTAS - a type of approximation algorithm that takes the approximation ratio as a parameter

    References

    1. ↑ Fomin, Fedor V.; Kaski, Petteri (March 2013), "Exact Exponential Algorithms", Communications of the ACM 56 (3): 80–88, doi:10.1145/2428556.2428575, http://cacm.acm.org/magazines/2013/3/161189-exact-exponential-algorithms/fulltext .
    2. ↑ Fomin, Fedor V.; Kratsch, Dieter (2010). Exact Exponential Algorithms. Springer. p. 203. ISBN 978-3-642-16532-0. https://archive.org/details/exactexponential00fvfo. 



    Retrieved from "https://handwiki.org/wiki/index.php?title=Exact_algorithm&oldid=42840"
    This article is licensed under CC BY-SA 3.0.
    Original source: https://handwiki.org/wiki/Exact algorithm
    Status: article is cached
    Encyclosphere.org EncycloReader is supported by the EncyclosphereKSF