OPT^{α} Approximation Algorithms 
Approximation Algorithms provide nonoptimal solutions for NPhard problems in polynomial time. The Approximation Factor indicates a how far the solution provided by the approximation algorithm is from the optimal solution, in the worst case. Formally, for a minimization problem, let ALG be the algorithm’s solution and OPT be the optimal solution. The approximation factor, R, is defined as the number for which
ALG ≤ R · OPT 
for any instance of the problem. Equivalently, maximization problems require
ALG ≥ R · OPT 
While some problems have approximation algorithms with a constant approximation factor, others only have algorithms with an R(n) approximation factor, which is a function of n, where n is the input length. Typically, R(n) is log(n) or n^{c}, for some constant c.
This thesis is concerned with such types of problems, and asks whether an algorithm with approximation factor which is function of OPT, rather than a function of n, exists. Concretely, this work concentrates on OPT^{α} approximation, and seeks for algorithms for which it is guaranteed that
ALG ≤ OPT^{α} 
for minimization problems, or
ALG ≥ OPT^{α} 
for maximization problems.
For some NPhard minimization problems it has been proven that no polynomial time approximation algorithm with a factor of n^{1−є} exists, for any є, under certain assumptions. For these problems, it is proven in the thesis that no OPT^{α} approximation polynomialtime algorithm exists, for any α, under the same assumptions.
Algorithms as well as hardness results for four NPhard problems are given in the thesis.
The objective of this problem is to partition a graph into cliques, such that the number of edges which cross between the cliques is minimized.
The problem has an O(log(n)) approximation algorithm.
A novel approximation algorithm is described in the thesis, for which it is proven that
ALG ≤ OPT + 2 · OPT^{2} 
The input for this problem consists of two symmetric square matrices, A and B, over Z^{+}, which have the same number of rows (and columns), n. The objective is to find a permutation π of 1 … n such that

 a_{i,j} · b_{π(i),πj} 
is minimized.
Two results are proven in the thesis for this problem.
Hardness of approximation: It is proven that, assuming P ≠ NP, no polynomial time algorithm, for which ALG < OPT^{2}, exists.
Quality of any solution: It is shown that, for a restricted version of the problem where every element in the matrices is greater than or equal to 1, any feasible solution is less than or equal OPT^{2}.
This problems is a formalization of a practical problem in the health domain. It is concerned with a large population, in which some individuals are suspected to be infected by a certain disease. Testing a blood sample has its cost, and testing blood samples of all the individuals might be expensive.
An alternative method is take many blood samples and put them all in one big tube, and test that tube. A negative result of that test means that no individual is infected (from those individuals that their blood sample was put in the tube). A positive result indicates that at least one individual is infected, but it is unknown who that individual is.
The objective is to construct a set of tests, such that after performing all the tests it is known exactly who is infected and who is not.
The version in the thesis is concerned with several diseases, rather than a single disease. Formally, the input consists:
A test is defined as follows. The test input is a subset of the n items. The test output is a boolean vector j of length m, where t[j] indicates whether at least on of the items in the input is infected by disease j, or not.
The objective is to find a minimal number of tests, such that after performing all the tests it is known for every individual in which disease it is infected, and in which disease it is not infected.
A new hardness of approximation result is provided in the thesis. This results utilizes a reduction from the Minimum Chromatic Number problem, for which it is shown that no OPT^{α} approximation algorithm exists under the assumption that ZPP ≠ NP. The result is that under the same assumption there does not exists a polynomialtime constantfactor approximation algorithm for the multi disease group testing problem.
The input of the K^{th} largest subset problem is:
A finite set A, a size, s(a_{i}) for each element a_{i} ∈ A, and a number K, such that K ≤ 2^{A}.
The objective is to find a number B, such that there exist K distinct subsets of A, and the sum of elements sizes in every such subset is less than or equal B.
This problem is NPhard. It is unknown whether it is in NP (in other words, even if P=NP it does not imply that this problem is solvable in polynomial time).
The thesis describes an approximation algorithm, which produces a solution of OPT^{(1+є)}, for any є>0. The algorithm’s runtime is O(n^{3+1/є}).
Note that such solution is analogous to PTAS in traditional approximation algorithms.
Many thanks again to my M.Sc. supervisor, Prof. Yonatan Aumann, for the helpful discussions.
opt to the power of alpha approximation algorithm
kth largest subset
Asher Stern Master Thesis
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.