Misplaced Pages

#88911

28-454: An approximation algorithm is called an f ( n ) {\displaystyle f(n)} -approximation algorithm for input size n {\displaystyle n} if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of f ( n ) {\displaystyle f(n)} times worse than the optimal solution. Here, f ( n ) {\displaystyle f(n)}

56-492: A polynomial-time approximation scheme ( PTAS ) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean traveling salesman problem ,

84-501: A PTAS is strictly contained in APX. One example of a problem with a PTAS is the bin packing problem . A problem is said to be APX-hard if there is a PTAS reduction from every problem in APX to that problem, and to be APX-complete if the problem is APX-hard and also in APX. As a consequence of P ≠ NP ⇒ PTAS ≠ APX, if P ≠ NP is assumed, no APX-hard problem has a PTAS. In practice, reducing one problem to another to demonstrate APX-completeness

112-399: A PTAS would produce a tour with length at most (1 + ε) L , with L being the length of the shortest tour. The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time O ( n ) or even O ( n ) counts as a PTAS. A practical problem with PTAS algorithms is that the exponent of

140-473: A PTAS), may be done by showing that the problem is APX-hard, after which the existence of a PTAS would show P = NP. APX-hardness is commonly shown via PTAS reduction or AP-reduction . MAX-3SAT MAX-3SAT is a problem in the computational complexity subfield of computer science . It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory . It

168-675: A PTAS-preserving reduction in a way that MAX-3SAT cannot. Proofs for explicit values of B include: all B ≥ 13, and all B ≥ 3 (which is best possible). Moreover, although the decision problem 2SAT is solvable in polynomial time, MAX-2SAT (3) is also APX-hard. The best possible approximation ratio for MAX-3SAT(B), as a function of B, is at least 7 / 8 + Ω ( 1 / B ) {\displaystyle 7/8+\Omega (1/B)} and at most 7 / 8 + O ( 1 / B ) {\displaystyle 7/8+O(1/{\sqrt {B}})} , unless NP = RP . Some explicit bounds on

196-452: A factor of 2 can be achieved with this simple algorithm, however: The Karloff-Zwick algorithm runs in polynomial-time and satisfies ≥ 7/8 of the clauses. While this algorithm is randomized, it can be derandomized using, e.g., the techniques from to yield a deterministic (polynomial-time) algorithm with the same approximation guarantees. The PCP theorem implies that there exists an ε > 0 such that (1- ε )-approximation of MAX-3SAT

224-513: A factor polynomial in the input size, includes max independent set in the general case. There also exist problems that are exp-APX-complete, where the approximation ratio is exponential in the input size. This may occur when the approximation is dependent on the value of numbers within the problem instance; these numbers may be expressed in space logarithmic in their value, hence the exponential factor. Polynomial-time approximation scheme In computer science (particularly algorithmics ),

252-406: A hardness between PTAS problems and APX-complete problems, and may be called APX-intermediate . The bin packing problem is thought to be APX-intermediate. Despite not having a known PTAS, the bin packing problem has several "asymptotic PTAS" algorithms, which behave like a PTAS when the optimum solution is large, so intuitively it may be easier than problems that are APX-hard. One other example of

280-727: A potentially APX-intermediate problem is min edge coloring . One can also define a family of complexity classes f ( n ) {\displaystyle f(n)} -APX, where f ( n ) {\displaystyle f(n)} -APX contains problems with a polynomial time approximation algorithm with a O ( f ( n ) ) {\displaystyle O(f(n))} approximation ratio. One can analogously define f ( n ) {\displaystyle f(n)} -APX-complete classes; some such classes contain well-known optimization problems. Log-APX-completeness and poly-APX-completeness are defined in terms of AP-reductions rather than PTAS-reductions; this

308-530: A single assignment of true/false values to the variables. Other APX-complete problems include: PTAS ( polynomial time approximation scheme ) consists of problems that can be approximated to within any constant factor besides 1 in time that is polynomial to the input size, but the polynomial depends on such factor. This class is a subset of APX. Unless P = NP , there exist problems in APX that are neither in PTAS nor APX-complete. Such problems can be thought of as having

SECTION 10

#1732858069089

336-488: Is NP-hard . Proof: Any NP-complete problem ⁠ L ∈ P C P ( O ( log ⁡ ( n ) ) , O ( 1 ) ) {\displaystyle L\in {\mathsf {PCP}}(O(\log(n)),O(1))} ⁠ by the PCP theorem . For x ∈ L , a 3-CNF formula Ψ x is constructed so that The Verifier V reads all required bits at once i.e. makes non-adaptive queries. This

364-435: Is an algorithm which takes an instance of an optimization or counting problem and a parameter ε > 0 and, in polynomial time, produces a solution that has a high probability of being within a factor ε of optimal. Conventionally, "high probability" means probability greater than 3/4, though as with most probabilistic complexity classes the definition is robust to variations in this exact value (the bare minimum requirement

392-481: Is because PTAS-reductions are not strong enough to preserve membership in Log-APX and Poly-APX, even though they suffice for APX. Log-APX-complete, consisting of the hardest problems that can be approximated efficiently to within a factor logarithmic in the input size, includes min dominating set when degree is unbounded. Poly-APX-complete, consisting of the hardest problems that can be approximated efficiently to within

420-576: Is being used; however, the constant under the big-O can still depend on ε arbitrarily. In other words, an EPTAS runs in FPT time where the parameter is ε. Even more restrictive, and useful in practice, is the fully polynomial-time approximation scheme or FPTAS , which requires the algorithm to be polynomial in both the problem size n and 1/ε . Unless P = NP , it holds that FPTAS ⊊ PTAS ⊊ APX . Consequently, under this assumption, APX-hard problems do not have PTASs. Another deterministic variant of

448-396: Is called the approximation ratio . Problems in APX are those with algorithms for which the approximation ratio f ( n ) {\displaystyle f(n)} is a constant c {\displaystyle c} . The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, f ( n ) {\displaystyle f(n)}

476-488: Is defined as: Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses. MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314). The decision version of MAX-3SAT is NP-complete . Therefore, a polynomial-time solution can only be achieved if P = NP . An approximation within

504-473: Is enough to prove the hardness of approximation ratio MAX-3SAT(B) is the restricted special case of MAX-3SAT where every variable occurs in at most B clauses. Before the PCP theorem was proven, Papadimitriou and Yannakakis showed that for some fixed constant B, this problem is MAX SNP-hard. Consequently, with the PCP theorem, it is also APX-hard. This is useful because MAX-3SAT(B) can often be used to obtain

532-524: Is generally greater than 1/2). Like a PTAS, a PRAS must have running time polynomial in n , but not necessarily in ε ; with further restrictions on the running time in ε , one can define an efficient polynomial-time randomized approximation scheme or EPRAS similar to the EPTAS, and a fully polynomial-time randomized approximation scheme or FPRAS similar to the FPTAS. The term PTAS may also be used to refer to

560-418: Is often done using other reduction schemes, such as L-reductions , which imply PTAS reductions. One of the simplest APX-complete problems is MAX-3SAT-3 , a variation of the Boolean satisfiability problem . In this problem, we have a Boolean formula in conjunctive normal form where each variable appears at most 3 times, and we wish to know the maximum number of clauses that can be simultaneously satisfied by

588-391: Is the found solution's score divided by the optimum solution's score, while for maximization problems the reverse is the case. For maximization problems, where an inferior solution has a smaller score, f ( n ) {\displaystyle f(n)} is sometimes stated as less than 1; in such cases, the reciprocal of f ( n ) {\displaystyle f(n)}

SECTION 20

#1732858069089

616-412: Is the ratio of the score of the found solution to the score of the optimum solution. A problem is said to have a polynomial-time approximation scheme ( PTAS ) if for every multiplicative factor of the optimum worse than 1 there is a polynomial-time algorithm to solve the problem to within that factor. Unless P = NP there exist problems that are in APX but without a PTAS, so the class of problems with

644-579: Is valid because the number of queries remains constant. Next we try to find a Boolean formula to simulate this. We introduce Boolean variables x 1 ,..., x l , where l is the length of the proof. To demonstrate that the Verifier runs in Probabilistic polynomial-time , we need a correspondence between the number of satisfiable clauses and the probability the Verifier accepts. It can be concluded that if this holds for every NP-complete problem then

672-528: The PCP theorem must be true. Håstad demonstrates a tighter result than Theorem 1 i.e. the best known value for ε . He constructs a PCP Verifier for 3-SAT that reads only 3 bits from the Proof. For every ε > 0, there is a PCP-verifier M for 3-SAT that reads a random string r of length ⁠ O ( log ⁡ ( n ) ) {\displaystyle O(\log(n))} ⁠ and computes query positions i r , j r , k r in

700-449: The PTAS is the quasi-polynomial-time approximation scheme or QPTAS . A QPTAS has time complexity n for each fixed ε > 0 . Furthermore, a PTAS can run in FPT time for some parameterization of the problem, which leads to a parameterized approximation scheme . Some problems which do not have a PTAS may admit a randomized algorithm with similar properties, a polynomial-time randomized approximation scheme or PRAS . A PRAS

728-399: The class of optimization problems that have a PTAS. PTAS is a subset of APX , and unless P = NP , it is a strict subset. Membership in PTAS can be shown using a PTAS reduction , L-reduction , or P-reduction , all of which preserve PTAS membership, and these may also be used to demonstrate PTAS-completeness. On the other hand, showing non-membership in PTAS (namely, the nonexistence of

756-406: The polynomial could increase dramatically as ε shrinks, for example if the runtime is O ( n ) . One way of addressing this is to define the efficient polynomial-time approximation scheme or EPTAS , in which the running time is required to be O ( n ) for a constant c independent of ε . This ensures that an increase in problem size has the same relative effect on runtime regardless of what ε

784-429: The proof π and a bit b r . It accepts if and only if 'π ( i r ) ⊕ π ( j r ) ⊕ π ( k r ) = b r . The Verifier has completeness (1− ε ) and soundness 1/2 + ε (refer to PCP (complexity) ). The Verifier satisfies If the first of these two equations were equated to "=1" as usual, one could find a proof π by solving a system of linear equations (see MAX-3LIN-EQN ) implying P = NP . This

#88911