Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Fully polynomial-time approximation scheme (view)

searching for Polynomial-time approximation scheme 9 found (76 total)

alternate case: polynomial-time approximation scheme

Subset sum problem (3,781 words) [view diff] no match in snippet view article find links to article

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S {\displaystyle S} of integers

Cut (graph theory) (1,132 words) [view diff] exact match in snippet view article

max-cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme for it unless P = NP. However, it can be approximated to

Weak NP-completeness (429 words) [view diff] no match in snippet view article find links to article

pseudo-polynomial time algorithm. It also does not have a fully-polynomial time approximation scheme. An example is the 3-partition problem. Both strong NP-hardness

Pseudo-polynomial time (876 words) [view diff] no match in snippet view article find links to article

pseudo-polynomial time algorithm. It also does not have a fully-polynomial time approximation scheme. An example is the 3-partition problem. Both strong NP-hardness

Parallel task scheduling (2,520 words) [view diff] exact match in snippet view article find links to article

{\displaystyle (2-1/m)} times the optimum preemptive makespan. A polynomial-time approximation scheme (PTAS) for the case when the number m {\displaystyle m} of

Approximation error (2,701 words) [view diff] case mismatch in snippet view article find links to article

computation when η is extremely small), is known as a Fully Polynomial-Time Approximation Scheme (FPTAS). The dependence on 1/η rather than log(1/η) is a

Maximum cut (3,125 words) [view diff] exact match in snippet view article find links to article

The Max-Cut Problem is APX-hard, meaning that there is no polynomial-time approximation scheme (PTAS), arbitrarily close to the optimal solution, for it

Configuration linear program (2,459 words) [view diff] no match in snippet view article find links to article

Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Algorithms and Computation. Lecture Notes

Minimum-weight triangulation (3,289 words) [view diff] no match in snippet view article find links to article

Semantic Scholar. Remy, Jan; Steger, Angelika (2009), "A quasi-polynomial time approximation scheme for minimum weight triangulation", Journal of the ACM, 56