On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear syste
- PDF / 180,211 Bytes
- 14 Pages / 595.276 x 793.701 pts Page_size
- 38 Downloads / 159 Views
ON THE APPROXIMATION RATIO THRESHOLD FOR THE REOPTIMIZATION OF THE MAXIMUM NUMBER OF SATISFIED EQUATIONS IN LINEAR SYSTEMS OVER A FINITE FIELD UDC 519.854
V. A. Mikhailyuk
Abstract. When an arbitrary equation is inserted into a linear system over the field GF ( 2) that contains exactly 3 variables from the set of n variables in each equation, the problem of the maximum number of satisfied equations is reoptimized with approximation ratio 3/2. This approximation ratio is a threshold. A similar result holds for systems that contain k variables in each equation when k = O ( log n ) . Keywords: C-approximation algorithm, reoptimization, discrete Fourier analysis, PCP theorem.
An arbitrary optimization problem P can be solved with the help of an efficient approximation algorithm. However, many optimization problems are NP-hard and, hence, it is unlikely that they can be solved exactly in polynomial time when P ¹ NP. Therefore, efficient approximation algorithms are considered with a view to solving such problems. For a maximization problem, a polynomial algorithm is considered as a C-approximation algorithm if, for an arbitrary instance, it yields a solution for which the value of the objective function is no smaller than OPT / C , where OPT is a global optimum. In this case, C is called an approximation ratio. A similar definition can be formulated for minimization problems. For a problem P, an upper bound on the approximation ratio C is established if there is a polynomial C-approximation algorithm for the solution of P. For this problem, a lower bound on the approximation ratio c is established if, for an arbitrary e > 0 , there is no polynomial approximation algorithm whose approximation ratio reaches c - e for P. If C = c , then an approximation ratio threshold ( C = c ) is established for the problem P. The corresponding algorithm is called an optimal (or threshold) approximation algorithm. The problem of establishment of lower bounds on approximation ratios is an intractable problem. The term “inapproximability” or “hardness of approximation” is used for this problem. The technique for obtaining lower bounds on the approximation ratio for some problem being investigated lies in the construction of polynomial reducibility of some NP-hard problem to the problem being investigated with such properties. Positive instances of an NP-hard problem are new instances for which the value of the objective function is no smaller than c, and its negative instances are new instances for which the value of the objective function is no larger than s. Then it is arguable that the approximation of a problem with a ratio smaller than c / s is NP-hard. This can be obtained by purely combinatorial methods, but the well-known Probabilistically Checkable Proof theorem (PCP theorem) [1] and discrete Fourier analysis [2, 3] can also be efficiently used for property testing. In this paper, a method for obtaining approximation lower bounds for the Max - E 3 - Lin - 2 problem (on the maximum number of satisfied equations in three variable
Data Loading...
