Randomized Algorithms (Spring 2010)/Randomized approximation algorithms

From EtoneWiki
Jump to: navigation, search

Approximation Algorithms

An optimization problem consists of:

  • A set of valid instances (inputs).
  • Each instance defines a set of feasible solutions .
  • Each instance also defines an objective function .
  • The problem is specified to be either a minimization problem or a maximization problem. Given an instance , our goal is to find a feasible solution with the minimum (or maximum) value of .
Example: the - shortest path problem
  • Each instance is a (nonnegatively)weighted directed graph along with two distinct vertices .
  • Given an instance, the feasible solutions are the simple paths from to in .
  • The objective function is the length of the path, defined by the total weight of the path.
  • The problem is a minimization problem.

An optimization problem can be transformed to a decision problem by "thresholding". For example, the optimization problem: "Given an instance , find the with minimum ." can be transformed to a (parameterized) decision problem: "Given an instance , determine whether there exists an with ."

Given an optimization problem, we can certainly solve its decision version by solving the optimization problem itself. The converse is also true: we can find the optimum by making queries to the decision version. Through binary search, this can be done efficiently.

Coping with the NP-hardness

An optimization problem is an NP-hard optimization problem if its decision version is NP-hard. Many interesting optimization problems are NP-hard. There are basically two ways to deal with the hardness.

Heuristics
We just apply some heuristic ideas to search for the optimal solution. This might work pretty good on some natural instances. On the other hand, giving a theoretical explanation why the heuristic method performs well on your input instance is usually very hard.
Approximation algorithms
We design an algorithm with guaranteed worst-case running time, which approximates the optimum within a guaranteed approximation ratio.

Let denote the optimum of the instance .

For a minimization problem, for any instance , the algorithm returns a feasible solution , such that , where .

For a maximization problem, for any instance , the algorithm returns a feasible solution , such that , where .

Such an algorithm is called an -approximation algorithm for the optimization problem. The ratio is called the approximation ratio.

We are particularly interested in the approximation algorithms running in poly-time of the input size, for the NP-hard optimization problems.

Combinatorial approximation algorithms

Classic approximation algorithms are mostly combinatorial algorithms, which uses standard algorithm design techniques (e.g., greedy, dynamic programming, etc.). In addition to the time complexity, we have to bound the approximation ratio.

We will introduce two examples, the minimum makespan scheduling, and the knapsack problem.

Scheduling

Scheduling is a class of problems. We consider a central problem in scheduling theory: the minimum makespan scheduling.

Problem (Minimum makespan scheduling)
Given processing times for jobs, , and an integer , find an assignment of the jobs to identical machines so that the completion time, also called the makespan, is minimum.
Formally, given as input a sequence and an integer , find an such that is minimized.

This problem is known to be NP-hard. We consider a very simple and natural algorithm:

  • Schedule the jobs one by one, in an arbitrary order, each job being assigned to a machine with least amount of work so far.

This algorithms is due to Graham (1966), who also shows that the algorithm approximates the optimal makespan within a factor of 2.

Let OPT be the optimal makespan. We have two observations:

  • , i.e. the optimal makespan is no smaller than the average processing time.
  • , i.e. the optimal makespan is no smaller than the largest processing time.

Proof of the approximation factor: We assume that the last job scheduled is , assigned to machine , and the makespan produced by the algorithm is . Since the algorithm assigns a job to the least loaded machine, right before is scheduled, machine whose current load is , must be the least loaded. Thus, is no greater than the average processing time. Then,

.

And since , it holds that .

There are poly-time algorithm using different ideas with much better approximation ratio for this problem.

Knapsack

Problem (Knapsack)
Given a set of objects, each with specified weight and profit , and a knapsack capacity , find a subset of objects whose total weight is bounded by and total profits is maximized.

A heuristic for the problem is to sort the objects by decreasing ratio of profit to weight, and then greedily pick objects in this order. However, the ratio between the solution of this heuristic and the OPT can be made arbitrarily bad. This is left as an exercise.

A pseudo-polynomial time algorithm by dynamic programming

Let be the largest possible total profit. We first minimize the total weight for each possible total profit value .

For each and , let denote a subset of the first objects whose total profit is exactly and whose total weight is minimized.

Let be the total weight of the set ( if no such set exists). Clearly is known for every . The following recurrence holds:

By dynamic programming, we can compute all values by constructing the matrix in an appropriate order. This takes totally time.

The optimal profit is given by .

Did we just solve an NP-hard problem in polynomial time, and prove that P=NP?

Actually, no, because of the factor in the time complexity. A poly-time algorithm, by definition, is that the worst-case running time is bounded with a polynomial of the size of the input, where the input is represented in binary.

The binary representation of the input of the knapsack problem only takes about size, which means that the above algorithm is not poly-time. However, if we represent the input in the unary (一进制) form, it takes unary bits to represent the inputs. With unary representation of the input, our algorithm is poly-time. An algorithm with this property is called a pseudo-polynomial time algorithm.

An FPTAS by by "rounding and scaling"

We notice that the above dynamic programming algorithm is poly-time if the total profit of sets of objects only has many possible values, and thus the matrix filled by the dynamic programming, is only polynomially large.

This leads us to an approximation algorithm by approximating all the profits to nearby lattice points. The idea is informally called the "rounding and scaling" technique:

Algorithm
  1. Given , let , where .
  2. For each object , let .
  3. With these new profits of objects, using the dynamic programming algorithm, find the most profit set, say .
  4. Return .

The following lemma bounds the approximation ratio of the algorithm. The algorithm takes as input an instance of the knapsack problem and a parameter , and returns a knapset solution with approximation ratio of (it is a maximization problem, so the approximation ratio is less than 1).

Lemma
Let be the output of the algorithm, and be the total profit of the objects in . Then
.
Proof.
Let be the optimal set. For any object , because of rounding down as , it holds that
, and equivalently .

Therefore,

.

The dynamic programming algorithm returns the optimal solution for the new profits . Therefore,

The running time of the approximation algorithm depends on the size of the matrix of dynamic programming, which is

.

Therefore, the algorithm finds a solution with a total profit at least in time polynomial of and , for any . This is called a fully polynomial-time approximation scheme (FPTAS). This is the best we can expect from a poly-time algorithm assuming that PNP.

LP-based approximation algorithms

A more advanced technique for designing approximation algorithms is linear programming. Many combinatorial optimization problems can be stated as integer programs (IP). The integer programs can be relaxed to linear programming problems. A feasible solution to the LP-relaxation is a fractional solution to the original combinatorial problem.

However, in the case of an NP-hard problem, we cannot expect the LP-relaxation has the same optimal solution as the original integer program (or otherwise a poly-time algorithm would solve an NP-hard problem). Thus, our task is not to look for an optimal solution to the LP-relaxation, but rather an integral solution which approximate the optimum within some bounded ratio.

There are two fundamental techniques for designing approximation algorithms using linear programming:

  • The first is to solve the LP-relaxation and convert the fractional optimal solution to an integral solution, with bounded approximation ratio to the optimal integral solution. This technique is called rounding.
  • The second is less obvious but with deeper insight, which uses the idea of duality. This technique is called the primal-dual schema.

We will focus on the rounding technique and demonstrate the power of randomized rounding. For other uses of LP for designing approximation algorithms, please refer to the classic textbook "Approximation Algorithms" by Vazirani.

Randomized Rounding

The integrality gap

Given an LP-relaxation for a minimization problem, let be the cost of an optimal solution to instance , and let denote the cost of an optimal fractional solution to instance , i.e., the value of the objective function of an optimal solution to the LP-relaxation. The integrality gap is defined to be

The integrality gap for a maximization problem can be defined similarly.

Max-SAT

We consider the Max-SAT problem:

Problem (Max-SAT)
Given a conjunctive normal form (CNF) formula of clauses defined on boolean variables , find a truth assignment to the boolean variables that maximizes the number of satisfied clauses.

and obtain two approximation algorithms by two different techniques.

The probabilistic method

A straightforward way to solve Max-SAT is to uniformly and independently assign each variable a random truth assignment. We have learned in the lecture about the probabilistic method that this "algorithm" has fine expected performance. Specifically, a clause of distinct variables is unsatisfied only if every one of the variables has the wrong "guess". The probability of this bad event is , thus the clause is satisfied with probability . Due to the linearity of expectation, expectedly at least clauses are satisfied.

We will see that by randomized rounding an LP, we can have a better approximation ratio.

LP relaxation + randomized rounding

For a clause , let be the set of indices of the variables that appear in the uncomplemented form in clause , and let be the set of indices of the variables that appear in the complemented form in clause . The Max-SAT problem can be formulated as the following integer linear programing.

Each in the programing indicates the truth assignment to the variable , and each indicates whether the claus is satisfied. The inequalities ensure that a clause is deemed to be true only if at least one of the literals in the clause is assigned the value 1.

The integer linear programming is relaxed to the following linear programming:

Let and be the fractional optimal solutions to the above linear programming. Clearly, is an upper bound on the optimal number of satisfied clauses.

Apply a very natural randomized rounding scheme. For each , independently

Correspondingly, each is assigned to TRUE independently with probability .

Lemma
Let be a clause with literals. The probability that it is satisfied by randomized rounding is at least
.
Proof.
Without loss of generality, we assume that all variables appear in in the uncomplemented form, and we assume that
.

The complemented cases are symmetric.

Clause remains unsatisfied by randomized rounding only if every one of , , is assigned to FALSE, which corresponds to that every one of , , is rounded to 0. This event occurs with probability . Therefore, the clause is satisfied by the randomized rounding with probability

.

By the linear programming constraints,

.

Then the value of is minimized when all are equal and . Thus, the probability that is satisfied is

,

where the last inequality is due to the concaveness of the function of variable .

For any , it holds that . Therefore, by the linearity of expectation, the expected number of satisfied clauses by the randomized rounding, is at least

.

The inequality is due to the fact that are the optimal fractional solutions to the relaxed LP, thus are no worse than the optimal integral solutions.

Let the two algorithms compete with each other

For any instance of the Max-SAT, let be the expected number of satisfied clauses when each variable is independently set to TRUE with probability ; and let be the expected number of satisfied clauses when we use the linear programming followed by randomized rounding.

We will show that on any instance of the Max-SAT, one of the two algorithms is a -approximation algorithm.

Theorem
Proof.
It suffices to show that . Letting denote the set of clauses that contain literals, we know that

By the analysis of randomized rounding,

Thus

An easy calculation shows that for any , so that we have