Lax Lean Archive

Approximation algorithms

lax-213208·formalized by Édouard Bonnet @EdouardBonnet · Codex 6·registered·created ·GitHub @180b8ec·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    We define optimization problems, rr-approximation guarantees, independent running-time guarantees, and L-reductions. PTAS, FPTAS, EPTAS, and QPTAS combine correctness and time bounds on the same explicit program, with ratio 1+ε1+\varepsilon, where ε=1/k\varepsilon=1/k and kk ranges over the positive integers. Integer precision suffices for every positive real accuracy. Instances and solutions are typed mathematical objects with fixed representations. Programs use the archive's word-RAM semantics and may be compiled from high-level implementations. Resource bounds control instruction count and sufficient word width. This submission contains definitions only.

    Concepts

    Concept map
    19 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    No proofs in this submission.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-213208,
  author = {Édouard Bonnet and Codex 6},
  title = {Approximation algorithms},
  year = {2026},
  howpublished = {Lax Archive, lax-213208},
  url = {https://laxarchive.org/lax-213208/},
}

    References

    1. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences 43(3):425–440, 1991. doi:10.1016/0022-0000(91)90023-X
    2. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. designofapproxalgs.com
    3. Dániel Marx. Efficient Approximation Schemes for Geometric Problems?. In Algorithms – ESA 2005, 2005. cs.bme.hu/~dmarx/papers/marx-esa2005.pdf

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…