|OPT|α Approximation Algorithms
Summary of M.Sc. Thesis

Asher Stern

1  General Idea

Approximation Algorithms provide non-optimal solutions for NP-hard 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 nc, 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.

2  General Hardness of Approximation Result

For some NP-hard minimization problems it has been proven that no polynomial time approximation algorithm with a factor of n1−є exists, for any є, under certain assumptions. For these problems, it is proven in the thesis that no |OPT|α approximation polynomial-time algorithm exists, for any α, under the same assumptions.

3  Results for NP-hard Problems

Algorithms as well as hardness results for four NP-hard problems are given in the thesis.

3.1  Minimum edge clique partition

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

3.2  Quadratic assignment problem

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

 ai,j · bπ(i),πj

is minimized.

Two results are proven in the thesis for this problem.

Hardness of approximation: It is proven that, assuming PNP, 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.

3.3  Minimum multi disease group testing

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 ZPPNP. The result is that under the same assumption there does not exists a polynomial-time constant-factor approximation algorithm for the multi disease group testing problem.

3.4  Kth largest subset

The input of the Kth largest subset problem is:
A finite set A, a size, s(ai) for each element aiA, 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 NP-hard. 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 run-time is O(n3+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.

A  Some words that might help search engines to find this page

opt to the power of alpha approximation algorithm
kth largest subset
Asher Stern Master Thesis

Back to home page

This document was translated from LATEX by HEVEA.