Bin-Packing
Asymptotic PTAS for Bin-Packing
Vahan Mkrtchyan1
1 Lane Department of Computer Science and Electrical Engineering
West Virginia University
March 21, 2014
Bin-Packing
Outline
Outline
1
Preliminaries
Bin-Packing
Outline
Outline
1
Preliminaries
2
Problem definition
Bin-Packing
Outline
Outline
1
Preliminaries
2
Problem definition
3
Definitions of PTAS, FPTAS and
Asymptotic FPTAS
Bin-Packing
Outline
Outline
4
1
Preliminaries
2
Problem definition
3
Definitions of PTAS, FPTAS and
Polynomial algorithm for restricted
instances
Asymptotic FPTAS
Bin-Packing
Outline
Outline
4
1
Preliminaries
2
Problem definition
3
Definitions of PTAS, FPTAS and
Asymptotic FPTAS
5
Polynomial algorithm for restricted
instances
Approximation algorithm for restricted
instances
Bin-Packing
Outline
Outline
4
1
Preliminaries
2
Problem definition
3
Definitions of PTAS, FPTAS and
Asymptotic FPTAS
5
Polynomial algorithm for restricted
instances
Approximation algorithm for restricted
instances
6
Asymptotic PTAS for Bin Packing
Bin-Packing
Preliminaries
Topics
Bin-Packing
Preliminaries
Topics
Outline
Bin-Packing
Preliminaries
Topics
Outline
1
Problem definition.
Bin-Packing
Preliminaries
Topics
Outline
1
Problem definition.
2
Definition of PTAS, FPTAS and Asymptotic PTAS.
Bin-Packing
Preliminaries
Topics
Outline
1
Problem definition.
2
Definition of PTAS, FPTAS and Asymptotic PTAS.
3
Polynomial algorithm for restricted instances.
Bin-Packing
Preliminaries
Topics
Outline
1
Problem definition.
2
Definition of PTAS, FPTAS and Asymptotic PTAS.
3
Polynomial algorithm for restricted instances.
4
Approximation algorithm for restricted instances.
Bin-Packing
Preliminaries
Topics
Outline
1
Problem definition.
2
Definition of PTAS, FPTAS and Asymptotic PTAS.
3
Polynomial algorithm for restricted instances.
4
Approximation algorithm for restricted instances.
5
Asymptotic PTAS for Bin Packing.
Bin-Packing
Problem definition
Problem definition
Problem Statement
We are given n objects of sizes {s1 , s2 , . . . sn }, such that 0 < si ≤ 1 and an unlimited supply of
unit sized bins.
Bin-Packing
Problem definition
Problem definition
Problem Statement
We are given n objects of sizes {s1 , s2 , . . . sn }, such that 0 < si ≤ 1 and an unlimited supply of
unit sized bins. The goal is to pack the objects into bins, minimizing the number of bins used.
Bin-Packing
Definitions of PTAS, FPTAS and Asymptotic FPTAS
PTAS, FPTAS and Asymptotic PTAS
Definition
A PTAS for a minimization problem Π is an algorithm A, which on all instances I of Π and
error-parameter ε > 0, returns a solution of cost A(I ), such that A(I ) ≤ (1 + ε) · OPT .
Bin-Packing
Definitions of PTAS, FPTAS and Asymptotic FPTAS
PTAS, FPTAS and Asymptotic PTAS
Definition
A PTAS for a minimization problem Π is an algorithm A, which on all instances I of Π and
error-parameter ε > 0, returns a solution of cost A(I ), such that A(I ) ≤ (1 + ε) · OPT . The
running time of the algorithm must be polynomial for each fixed value of ε .
Bin-Packing
Definitions of PTAS, FPTAS and Asymptotic FPTAS
PTAS, FPTAS and Asymptotic PTAS
Definition
A PTAS for a minimization problem Π is an algorithm A, which on all instances I of Π and
error-parameter ε > 0, returns a solution of cost A(I ), such that A(I ) ≤ (1 + ε) · OPT . The
running time of the algorithm must be polynomial for each fixed value of ε .
Definition
An FPTAS for a minimization problem Π is a PTAS that runs in time, that is polynomial from the
size of the input instance and ε1 .
Bin-Packing
Definitions of PTAS, FPTAS and Asymptotic FPTAS
PTAS, FPTAS and Asymptotic PTAS
Definition
A PTAS for a minimization problem Π is an algorithm A, which on all instances I of Π and
error-parameter ε > 0, returns a solution of cost A(I ), such that A(I ) ≤ (1 + ε) · OPT . The
running time of the algorithm must be polynomial for each fixed value of ε .
Definition
An FPTAS for a minimization problem Π is a PTAS that runs in time, that is polynomial from the
size of the input instance and ε1 .
Definition
An asymptotic PTAS for a minimization problem Π is an algorithm A, which on all instances I of
Π and error-parameter ε > 0, returns a solution of cost A(I ), such that
A(I ) ≤ (1 + ε) · OPT + C (ε).
Bin-Packing
Definitions of PTAS, FPTAS and Asymptotic FPTAS
PTAS, FPTAS and Asymptotic PTAS
Definition
A PTAS for a minimization problem Π is an algorithm A, which on all instances I of Π and
error-parameter ε > 0, returns a solution of cost A(I ), such that A(I ) ≤ (1 + ε) · OPT . The
running time of the algorithm must be polynomial for each fixed value of ε .
Definition
An FPTAS for a minimization problem Π is a PTAS that runs in time, that is polynomial from the
size of the input instance and ε1 .
Definition
An asymptotic PTAS for a minimization problem Π is an algorithm A, which on all instances I of
Π and error-parameter ε > 0, returns a solution of cost A(I ), such that
A(I ) ≤ (1 + ε) · OPT + C (ε). The running time of the algorithm must be polynomial for each
fixed value of ε .
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K .
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Proof.
(Sketch). We will show that the number of feasible packings is at most polynomial.
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Proof.
(Sketch). We will show that the number of feasible packings is at most polynomial.
(1) The number of items in a bin is at most M = b ε1 c.
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Proof.
(Sketch). We will show that the number of feasible packings is at most polynomial.
(1) The number of items in a bin is at most M = b ε1 c.
(2) The number of different bin-types is at most R =
˜
K
M
=
K +M −1
M
.
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Proof.
(Sketch). We will show that the number of feasible packings is at most polynomial.
(1) The number of items in a bin is at most M = b ε1 c.
(2) The number of different bin-types is at most R =
˜
K
M
=
K +M −1
M
.
(3) No more than n bins are needed in a feasible solution of any instance.
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Proof.
(Sketch). We will show that the number of feasible packings is at most polynomial.
(1) The number of items in a bin is at most M = b ε1 c.
(2) The number of different bin-types is at most R =
˜
K
M
=
K +M −1
M
.
(3) No more than n bins are needed in a feasible solution of any instance.
(4) The number of feasible packings is at most
˜
R
=
n
R +n−1
n
=
R +n−1
R −1
= O (nR −1 ).
Bin-Packing
Polynomial algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε , and the number of
different item-sizes is K . Then there is a polynomial algorithm for solving these instances.
Proof.
(Sketch). We will show that the number of feasible packings is at most polynomial.
(1) The number of items in a bin is at most M = b ε1 c.
(2) The number of different bin-types is at most R =
˜
K
M
=
K +M −1
M
.
(3) No more than n bins are needed in a feasible solution of any instance.
(4) The number of feasible packings is at most
˜
R
=
n
R +n−1
n
=
R +n−1
R −1
= O (nR −1 ).
Clearly, we can go through all of them, and find the one that uses minimum number of bins.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε .
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Sort the sizes of the items of the input instance I as follows: s1 ≤ s2 ≤ ... ≤ sn .
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Sort the sizes of the items of the input instance I as follows: s1 ≤ s2 ≤ ... ≤ sn .
Partition the items into K groups, each of which is of size Q (except may be the last one).
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Sort the sizes of the items of the input instance I as follows: s1 ≤ s2 ≤ ... ≤ sn .
Partition the items into K groups, each of which is of size Q (except may be the last one).
Consider the new instance J of bin packing obtained from I by rounding the size of each
element to the maximum size of its group.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Sort the sizes of the items of the input instance I as follows: s1 ≤ s2 ≤ ... ≤ sn .
Partition the items into K groups, each of which is of size Q (except may be the last one).
Consider the new instance J of bin packing obtained from I by rounding the size of each
element to the maximum size of its group.
Solve the instance J by previous algorithm.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Sort the sizes of the items of the input instance I as follows: s1 ≤ s2 ≤ ... ≤ sn .
Partition the items into K groups, each of which is of size Q (except may be the last one).
Consider the new instance J of bin packing obtained from I by rounding the size of each
element to the maximum size of its group.
Solve the instance J by previous algorithm.
Return the packing of J as a packing of I.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Theorem
Consider the instances of bin packing, in which the sizes of items are ≥ ε . Then there is a
(1 + ε)-approximation algorithm for solving these instances.
The Algorithm
Let K = d ε12 e and Q = bn · ε 2 c.
Sort the sizes of the items of the input instance I as follows: s1 ≤ s2 ≤ ... ≤ sn .
Partition the items into K groups, each of which is of size Q (except may be the last one).
Consider the new instance J of bin packing obtained from I by rounding the size of each
element to the maximum size of its group.
Solve the instance J by previous algorithm.
Return the packing of J as a packing of I.
Remark
Observe that the packing returned by the algorithm is a feasible packing of I.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
OPT (JQ ) + Q
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
≤
OPT (JQ ) + Q
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
OPT (JQ ) + Q
≤
0
OPT (JQ
)+Q
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
OPT (JQ ) + Q
≤
0
OPT (JQ
)+Q
≤
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
OPT (JQ ) + Q
≤
0
OPT (JQ
)+Q
≤
OPT (J 0 ) + Q
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
OPT (JQ ) + Q
≤
0
OPT (JQ
)+Q
≤
OPT (J 0 ) + Q
≤
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Instances
I-the input instance.
J- the instance constructed by the algorithm.
J 0 - the instance obtained from I by rounding the size of each element to the minimum size
of its group.
JQ - the instance obtained from J by removing the last Q items.
0 - the instance obtained from J 0 by removing the first Q items.
JQ
The Analysis
OPT (J )
≤
OPT (JQ ) + Q
≤
0
OPT (JQ
)+Q
≤
OPT (J 0 ) + Q
≤
OPT (I ) + Q .
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
≤
bn · ε 2 c
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
n
i =1
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
n
i =1
≤
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Therefore:
OPT (J )
≤
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Therefore:
OPT (J )
≤
OPT (I ) + Q
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Therefore:
OPT (J )
≤
≤
OPT (I ) + Q
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Therefore:
OPT (J )
≤
OPT (I ) + Q
≤
OPT (I ) + ε · OPT
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Therefore:
OPT (J )
≤
OPT (I ) + Q
≤
OPT (I ) + ε · OPT
=
Bin-Packing
Approximation algorithm for restricted instances
Restricted Instances
Some Bounds
Q
=
bn · ε 2 c
≤
n · ε2
≤
ε · ∑ si
≤
ε · OPT .
n
i =1
Therefore:
OPT (J )
≤
OPT (I ) + Q
≤
OPT (I ) + ε · OPT
=
(1 + ε) · OPT .
Bin-Packing
Asymptotic PTAS for Bin Packing
The General Case
Theorem
There exists a polynomial algorithm that for each ε ∈ (0, 12 ] finds a packing with the number of
bins at most (1 + 2 · ε) · OPT + 1.
Bin-Packing
Asymptotic PTAS for Bin Packing
The General Case
Theorem
There exists a polynomial algorithm that for each ε ∈ (0, 12 ] finds a packing with the number of
bins at most (1 + 2 · ε) · OPT + 1. In other words, bin packing problem admits an asymptotic
PTAS.
Bin-Packing
Asymptotic PTAS for Bin Packing
The General Case
Theorem
There exists a polynomial algorithm that for each ε ∈ (0, 12 ] finds a packing with the number of
bins at most (1 + 2 · ε) · OPT + 1. In other words, bin packing problem admits an asymptotic
PTAS.
The Algorithm
For the input instance I consider the instance I 0 obtained from I by removing all items of
size less than ε .
Bin-Packing
Asymptotic PTAS for Bin Packing
The General Case
Theorem
There exists a polynomial algorithm that for each ε ∈ (0, 12 ] finds a packing with the number of
bins at most (1 + 2 · ε) · OPT + 1. In other words, bin packing problem admits an asymptotic
PTAS.
The Algorithm
For the input instance I consider the instance I 0 obtained from I by removing all items of
size less than ε .
Solve I 0 by the previous (1 + ε)-approximation algorithm.
Bin-Packing
Asymptotic PTAS for Bin Packing
The General Case
Theorem
There exists a polynomial algorithm that for each ε ∈ (0, 12 ] finds a packing with the number of
bins at most (1 + 2 · ε) · OPT + 1. In other words, bin packing problem admits an asymptotic
PTAS.
The Algorithm
For the input instance I consider the instance I 0 obtained from I by removing all items of
size less than ε .
Solve I 0 by the previous (1 + ε)-approximation algorithm.
Apply First-Fit on the resulting packing using the items from I − I 0 .
Bin-Packing
Asymptotic PTAS for Bin Packing
The General Case
Theorem
There exists a polynomial algorithm that for each ε ∈ (0, 12 ] finds a packing with the number of
bins at most (1 + 2 · ε) · OPT + 1. In other words, bin packing problem admits an asymptotic
PTAS.
The Algorithm
For the input instance I consider the instance I 0 obtained from I by removing all items of
size less than ε .
Solve I 0 by the previous (1 + ε)-approximation algorithm.
Apply First-Fit on the resulting packing using the items from I − I 0 .
Return the resulting packing.
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm.
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ),
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
The Analysis: Extra Bins Were Required
The room in the first L − 1 bins is less than ε .
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
The Analysis: Extra Bins Were Required
The room in the first L − 1 bins is less than ε . Then:
OPT
≥
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
The Analysis: Extra Bins Were Required
The room in the first L − 1 bins is less than ε . Then:
n
OPT
≥
∑ si
i =1
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
The Analysis: Extra Bins Were Required
The room in the first L − 1 bins is less than ε . Then:
n
OPT
≥
∑ si
i =1
>
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
The Analysis: Extra Bins Were Required
The room in the first L − 1 bins is less than ε . Then:
n
OPT
≥
∑ si
i =1
>
(L − 1) · (1 − ε)
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Analysis
Let L be the number of bins returned by the algorithm. If no extra bin was required for packing
the items from I − I 0 , then L ≤ (1 + ε) · OPT (I 0 ) ≤ (1 + ε) · OPT (I ), hence we can assume that
extra bins were required.
The Analysis: Extra Bins Were Required
The room in the first L − 1 bins is less than ε . Then:
n
OPT
≥
∑ si
i =1
>
or
L<
(L − 1) · (1 − ε)
OPT
1−ε
+ 1.
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
1
1−ε
· ((1 − ε)(1 + 2 · ε) − 1)
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
=
1
1−ε
· ((1 − ε)(1 + 2 · ε) − 1)
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
=
1
1−ε
1
1−ε
· ((1 − ε)(1 + 2 · ε) − 1)
· (1 + ε − 2 · ε 2 − 1)
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
=
=
1
1−ε
1
1−ε
· ((1 − ε)(1 + 2 · ε) − 1)
· (1 + ε − 2 · ε 2 − 1)
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
=
=
1
1−ε
1
1−ε
ε
1−ε
· ((1 − ε)(1 + 2 · ε) − 1)
· (1 + ε − 2 · ε 2 − 1)
· (1 − 2 · ε)
Bin-Packing
Asymptotic PTAS for Bin Packing
The Analysis of the Algorithm
The Final Bound
We need to show that OPT
+ 1 ≤ (1 + 2 · ε) · OPT + 1.
1−ε
1+2·ε −
1
1−ε
=
=
=
≥ 0.
1
1−ε
1
1−ε
ε
1−ε
· ((1 − ε)(1 + 2 · ε) − 1)
· (1 + ε − 2 · ε 2 − 1)
· (1 − 2 · ε)

需要 点、供給 点、辺容量を持つ 木を分割するアルゴ