Denition Knapsack problem
Introduction to approximation algorithms
Optimization Algorithms in Production Management
Huynh Tuong Nguyen
Faculty of Computer Science and Engineering Ho Chi Minh City University of Technology htnguyen@cse.hcmut.edu.vn
June 14, 2012
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Denition
Knapsack problem
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Combinatorial optimization problems
4-tuple (X , Y , Feas, Objective ) X : an input space, Y : a solution space, Feas : X Y {0, 1} a feasibility function, Objective : X Y R the objective function. Given an input instance x X , a solution y Y is feasible if Feas (x , y ) = 1. The focus of the problem is related to nding those y Y that are feasible and maximize (or minimize) the Objective function Obj (x , y ) among all feasible y : such a y is called optimum; we denote by OPT(x ) the value Obj (x , y ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Ecient algorithm
Heuristics One could try to come up with an algorithm that worked on typical instances of the problem. The problem with this approach is that it is hard to dene typical: there may be algorithms that work onmost instances, but yet real-life instances may come from a distribution that is mostly supported on the bad instances for this algorithm. Nevertheless, this approach is used commonly and in certain cases, one can demonstrate certain theoratical guarantees.
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Ecient algorithm
Approximation algorithm Given an input x X , a solution y Y is said to be an (1 + )-approximate solution if y is feasible and |Obj (x , y ) OPT (x )| OPT (x )
An algorithm A is said to be an -approximation algorithm if for each x X , the element A(x ) Y is an -approximate solution. The Combinatorial Optimization problem is said to be -approximable if it has a polynomial-time -approximation algorithm.
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Ecient algorithm
Approximation algorithm Given an input x X , a solution y Y is said to be an (1 + )-approximate solution if y is feasible and |Obj (x , y ) OPT (x )| OPT (x )
An algorithm A is said to be an -approximation algorithm if for each x X , the element A(x ) Y is an -approximate solution. The Combinatorial Optimization problem is said to be -approximable if it has a polynomial-time -approximation algorithm.
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Combinatorial optimization problems
Algorithmic problems Search problem: given as input x X , nd an optimum y . Computational problem: given x X , nd OPT(x ). Decision problem: given x X and k R, is OPT(x ) k ?
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
KNAPSACK problem
Input a set X of n items, each item i X has weight wi Z+ and value vi Z+ . A knapsack with capacity c Z+ . Output Find a subcollection of items S X such that Objective Maximize the total value of the subcollection
i S i S
wi c
vi c .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
KNAPSACK problem
Input a set X of n items, each item i X has weight wi Z+ and value vi Z+ . A knapsack with capacity c Z+ . Output Find a subcollection of items S X such that Objective Maximize the total value of the subcollection
i S i S
wi c
vi c .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
KNAPSACK problem
Input a set X of n items, each item i X has weight wi Z+ and value vi Z+ . A knapsack with capacity c Z+ . Output Find a subcollection of items S X such that Objective Maximize the total value of the subcollection
i S i S
wi c
vi c .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Greedy approach
Algorithm
1
sort items in non-increasing order of vi /wi , i.e. v[j ] /w[j ] v[j +1] /w[j +1]
2 3
nd the smallest k such that
i k
w [i ] > c ,
if v[k ] > i <k 1 v[i ] then output S = [k ] else output S = [1], [2], . . . , [k 1].
It can be shown that the above greedy approach yields a 2-approximation.
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Greedy approach
Algorithm
1
sort items in non-increasing order of vi /wi , i.e. v[j ] /w[j ] v[j +1] /w[j +1]
2 3
nd the smallest k such that
i k
w [i ] > c ,
if v[k ] > i <k 1 v[i ] then output S = [k ] else output S = [1], [2], . . . , [k 1].
It can be shown that the above greedy approach yields a 2-approximation.
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of 2-approximation algorithm
Let Z1 (x ) and Z2 (x ) be two objective values according to two choices in step c) with an instance x , Let Z (x ) be objective values given by the proposed algorithm Z (x ) = max{Z1 (x ), Z2 (x )} Since both of two choices in step c) give lower bounds and sum of them give an upperbound, solution corresponding to maximum value chosen OPT (x ) Z1 (x ) + Z2 (x ) 2 max{Z1 (x ), Z2 (x )} = 2Z (x ) OPT (x ) 2Z (x ) |OPT (x ) Z (x )| OPT (x ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of 2-approximation algorithm
Let Z1 (x ) and Z2 (x ) be two objective values according to two choices in step c) with an instance x , Let Z (x ) be objective values given by the proposed algorithm Z (x ) = max{Z1 (x ), Z2 (x )} Since both of two choices in step c) give lower bounds and sum of them give an upperbound, solution corresponding to maximum value chosen OPT (x ) Z1 (x ) + Z2 (x ) 2 max{Z1 (x ), Z2 (x )} = 2Z (x ) OPT (x ) 2Z (x ) |OPT (x ) Z (x )| OPT (x ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of 2-approximation algorithm
Let Z1 (x ) and Z2 (x ) be two objective values according to two choices in step c) with an instance x , Let Z (x ) be objective values given by the proposed algorithm Z (x ) = max{Z1 (x ), Z2 (x )} Since both of two choices in step c) give lower bounds and sum of them give an upperbound, solution corresponding to maximum value chosen OPT (x ) Z1 (x ) + Z2 (x ) 2 max{Z1 (x ), Z2 (x )} = 2Z (x ) OPT (x ) 2Z (x ) |OPT (x ) Z (x )| OPT (x ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of 2-approximation algorithm
Let Z1 (x ) and Z2 (x ) be two objective values according to two choices in step c) with an instance x , Let Z (x ) be objective values given by the proposed algorithm Z (x ) = max{Z1 (x ), Z2 (x )} Since both of two choices in step c) give lower bounds and sum of them give an upperbound, solution corresponding to maximum value chosen OPT (x ) Z1 (x ) + Z2 (x ) 2 max{Z1 (x ), Z2 (x )} = 2Z (x ) OPT (x ) 2Z (x ) |OPT (x ) Z (x )| OPT (x ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of 2-approximation algorithm
Let Z1 (x ) and Z2 (x ) be two objective values according to two choices in step c) with an instance x , Let Z (x ) be objective values given by the proposed algorithm Z (x ) = max{Z1 (x ), Z2 (x )} Since both of two choices in step c) give lower bounds and sum of them give an upperbound, solution corresponding to maximum value chosen OPT (x ) Z1 (x ) + Z2 (x ) 2 max{Z1 (x ), Z2 (x )} = 2Z (x ) OPT (x ) 2Z (x ) |OPT (x ) Z (x )| OPT (x ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of 2-approximation algorithm
Let Z1 (x ) and Z2 (x ) be two objective values according to two choices in step c) with an instance x , Let Z (x ) be objective values given by the proposed algorithm Z (x ) = max{Z1 (x ), Z2 (x )} Since both of two choices in step c) give lower bounds and sum of them give an upperbound, solution corresponding to maximum value chosen OPT (x ) Z1 (x ) + Z2 (x ) 2 max{Z1 (x ), Z2 (x )} = 2Z (x ) OPT (x ) 2Z (x ) |OPT (x ) Z (x )| OPT (x ).
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
FPTAS
There is a pseudo-polynomial time algorithm OPT-KNAPSACK that solves KNAPSACK optimally, i.e. in time poly (n, V ) = O (n2 V ) (by using dynamic programming algorithm). (1 + ) approximate algorithm for KNAPSACK
1
run OPT-KNAPSACK over the input x = {(vi , wi ), i = 1, 2, . . . , n} to obtain S , output S .
It can be shown that the above approach guaranties a relative distance of () according to optimal solution, i.e |Obj (x , y ) OPT (x )| OPT (x ).
OAPM N. Huynh Tuong Introduction to approximation algorithms
Denition Knapsack problem
FPTAS
There is a pseudo-polynomial time algorithm OPT-KNAPSACK that solves KNAPSACK optimally, i.e. in time poly (n, V ) = O (n2 V ) (by using dynamic programming algorithm). (1 + ) approximate algorithm for KNAPSACK
1
run OPT-KNAPSACK over the input x = {(vi , wi ), i = 1, 2, . . . , n} to obtain S , output S .
It can be shown that the above approach guaranties a relative distance of () according to optimal solution, i.e |Obj (x , y ) OPT (x )| OPT (x ).
OAPM N. Huynh Tuong Introduction to approximation algorithms
Denition Knapsack problem
FPTAS
There is a pseudo-polynomial time algorithm OPT-KNAPSACK that solves KNAPSACK optimally, i.e. in time poly (n, V ) = O (n2 V ) (by using dynamic programming algorithm). (1 + ) approximate algorithm for KNAPSACK
1
run OPT-KNAPSACK over the input x = {(vi , wi ), i = 1, 2, . . . , n} to obtain S , output S .
It can be shown that the above approach guaranties a relative distance of () according to optimal solution, i.e |Obj (x , y ) OPT (x )| OPT (x ).
OAPM N. Huynh Tuong Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
Denition Knapsack problem
Proof of FPTAS
Let
y : optimal solution of the modied instance x according to input x
vi K
1 vi
vi K
vi K Kvi vi Therefore, for any input x and any solution y : Obj (x , y ) K |x | KObj (x , y ) Obj (x , y ) (1) Obj (x , y ) KObj (x , y ) |x |K nK = LB OPT . From (1) we have also: KObj (x , y ) KObj (x , y ) Obj (x , y ). OPT (x ) Obj (x , y ) = Obj (x , y ) OPT . |OPT (x ) Obj (x , y )| OPT (since in a maximization problem, OPT (x ) Obj (x , y ) for any input x and any feasible solution y .
OAPM
N. Huynh Tuong
Introduction to approximation algorithms
