NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1

Size: px

Start display at page:

Download "NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1"

るるみすみだ
5 years ago
Views:

1 NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1

2 1 1 Avis & Fukuda [1] 2 NP (Ehrgott [3] ) ( ) 3 NP k c 1, c 2,..., c k 1 λ 1, λ 2,..., λ k 2

3 k i=1 λ ic i (λ 1,..., λ k ) 2 X, Y X Y = (X Y ) \ (X Y ) X Y G = (V, E) G V 1 T E c: E R + c G G T c(t ) = e T c(e) : MC-MCST : G = (V, E) k c 1,..., c k : E R + : G c 1,..., c k G c 1,..., c k ( MC-MCST ) 3 G = (V, E) e 1 E 2 1 e 1 1 e 1 2 E 1, E 2 E G E 1 E 2 MC-MCST : BinaryPartition : G = (V, E) 2 E 1, E 2 E k c 1,..., c k : E R + : E 1 E 2 G c 1,..., c k BinaryPartition MC-MCST 3.1. BinaryPartition NP 3

4 v t 1 v f 1 v t 2 v f 2 v t 3 v f 3 v t 4 v f 4 v1 r v2 r v3 r v4 r r w r 1 w q 1 w r 2 w q 2 w r 3 w q 3 u x1 1 u x2 1 u x3 1 u x2 2 u x3 2 u x1 3 u x3 3 u x4 3 1: 3.1 C 1 = x 1 x 2 x 3, C 2 = x 2 x 3. C 3 = x 1 x 3 x 4 C 1 C 2 C 3 E \ (E 1 E 2 ) E 1 E 2 1: {vi r, vt i } {vr i, vf i } {vt i, vf i } {vr i, r} {vr i, vt i } {vr i, vf i } {vi t, vf i } {vi r, r} c i 0 1 1/n /n 1 c i 1 0 1/n /n 1 {wj r, wq j } {wr j, r} {wq j, ul j } {wr j, ul j } c i 2 1/(2n) if l = x i, 2 otherwise c i 2 1/(2n) if l = x i, 2 otherwise. NP NP SAT ( ) BinaryPartition SAT x 1,..., x n C 1,..., C m 1 SAT G = (V, E) x i 3 v i r, vi, t v f i C j 2 w j, r w q j C j l 1 u l j 1 r G G x i {vi t, vf i } E 1, {vi r, vt i } E \ (E 1 E 2 ), {vi r, vf i } E\(E 1 E 2 ), {vi r, r} E 1 4 C j {wj r, wq j } E 2, {wj r, r} E 1 2 C j l {wj r, ul j } E\(E 1 E 2 ), {w q j, ul j} E 1 2 G E 1, E 2 1 2n ( ) x i c i x i c i 1 c i ({vi r, vt i }) = 0, c i({vi r, vf i }) = 1, c i({vi t, vf i }) = 1/n, c i({vi r, r}) = 1 i {1,..., n} \ {i} c i ({vi r, vt i }) = 0, c i({vi r, vf i }) = 0, c i ({vi t, vf i }) = 1/n, c i ({vi r, r}) = 1 j {1,..., m} C j l c i ({wj r, wq j }) = 2 1/(2n), c i({wj r, r}) = 1, 4

5 c i ({w q j, ul j }) = 1 c i ({w r j, ul j }) = { 1 (l = xi ) 2 ( ) c i ({vi r, vt i }) = 1, c i ({vr i, vf i }) = 0, c i ({vt i, vf i }) = 1/n, c i ({vr i, r}) = 1 i {1,..., n} \ {i} c i ({vi r, vt i }) = 0, c i ({vr i, vf i }) = 0, c i ({vi t, vf i }) = 1/n, c i ({vi r, r}) = 1 j {1,..., m} C j l c i ({wj r, wq j }) = 2 1/(2n), c i ({wj r, r}) = 1, c i ({wq j, ul j }) = 1 c i ({w r j, u l j}) = { 1 (l = xi ) 2 ( ) MC-MCST G T E 1 T T E 2 = i {1,..., n} G {vi r, vi} t {vi r, v f i } {vt i, v f i } E 1 j {1,..., m} G C j l 1 {wj, r u l j} c 1,..., c n, c 1,..., c n c c c i λ i c i λ i T c i {1,..., n} {vi r, vt i } λ i 1/n T {vi t, vf i } {vr i, vf i } G T {vi t, vf i } E 1 c(t ) c(t ) = n i =1 (λ i c i ({vr i, vf i }) + λ i c i ({vi r, vf i })) n i =1 (λ i c i ({vt i, vf i }) + λ i c i ({vi t, vf i })) = (λ i + 0) n i =1 (λ i /n + λ i /n) = λ i 1/n T c c(t ) c(t ) λ i 1/n T c i {1,..., n} {vi r, vf i } λ i 1/n n i =1 (λ i + λ i ) = 1 i {1,..., n} T {vi r, vt i } λ i = 1/n λ i = 0 T {vi r, vf i } λ i = 0 λ i = 1/n c i c i (i {1,..., n}) G SAT c = n i=1 (λ ic i + λ i c i ) T i {1,..., n} T {vi r, vi} t {vi r, v f i } SAT T {vi r, vi} t x i T {vi r, v f i } x i T G j {1,..., m} C j l 1 {wj r, ul j } T T c j {1,..., m} C j l {wj r, ul j } T l 5

6 SAT l T {wj, r u l j} {wj, r w q j } G ( ) T λ l = 0 c(t ) c(t ) = n i=1 (λ ic i ({wj, r w q j })+λ ic i ({wj, r w q j })) n i=1 (λ ic i ({w r j, u l j})+λ i c i ({w r j, u l j})) = n i=1 (λ i +λ i )(2 1/(2n)) ( n i=1 (2(λ i +λ i )) λ l ) = (2 1/(2n)) (2 0) = 1/(2n) < 0 T c G SAT x i λ i = 0, λ i = 1/n ( x i ) λ i = 1/n, λ i = 0 c = n i=1 (λ ic i + λ i c i ) i {1,..., n} c({r, vi r }) = 1 c({vi, t v f i }) = 1/n x i c({vi r, vi}) t = 0 c({vi r, v f i }) = 1/n x i c({vi r, vt i }) = 1/n c({vr i, vf i }) = 0 j {1,..., m} C j l c({r, wj r}) = 1, c({wr j, wq j }) = 2 1/(2n), c({wq j, ul j }) = 1 l c({wj r, ul j }) = 2 1/n l c({wr j, ul j }) = 2 j {1,..., m} C j l 1 T = E 1 {{vi r, vt i } x i } {{vi r, vf i } x i } {{wj r, ul j j } j {1,..., m}} G T c 4 MC-MCST G R R G R R R G G 2 T T T T 2 G G(G) ( MC-MCST ) G(G) G M (G) G M (G) 4.1. G G(G) G M (G) G(G) [9, Exercise ] G M (G) Ehrgott [2] 6

7 G M (G) R G e 1 e 2 e m G T λ T R k T c 1,..., c k λ T 4.2. G T λ T. λ T λ k λ i c i (e) e T i=1 e T k λ i = 1, i=1 λ i 0 k λ i c i (e) (T T ), i=1 (i {1,..., k}). 1 G T ( ) T O(m 2 ) i {1,..., k} λ i G T λ T R R R λ R (λ R ) 1 = 1 i {2,..., k} (λ R ) i = 0 R c 1 c 1 R R G T 2 λ T = (1, 0, 0,..., 0) T R c 1 T 1 R 1 c G = (V, E) c: E R + T 1, T 2 E c G 2 e 1 T 1 \ T 2 e 2 T 2 \ T 1 (T 2 {e 1 }) \ {e 2 } c G. e 1, e 2 e 1 T 1 \ T 2 T 1 \ T 2 e c(e) T 2 {e 1 } e 2 T 2 \ T 1 e 1 e c(e) 7

8 e 2 T = (T 1 {e 1 }) \ {e 2 } G c(e 1 ) < c(e 2 ) c(t ) = c(t 2 ) + c(e 1 ) c(e 2 ) < c(t 2 ) T 2 c c(e 1 ) > c(e 2 ) e 1 e T 1 \ T 2 c(e) > c(e 2 ) T 1 {e 2 } T 1 \ T 2 T 1 T 1 c(e 1 ) = c(e 2 ) c(t ) = c(t 1 ) = c(t 2 ) T R\T e c 1 (e) e R T {e R } T \ R e c 1 (e) e T T = (T {e R }) \ {e T } T R T < R T T T T 2 λ T (1, 0, 0,..., 0) λ T j {2,..., k} (λ T ) j 0 λ T 1 ε > 0 j ε µ R k ε µ 2 k i=1 µ ic i G S S λ T µ λ T S T ε S c = k i=1 (λ T ) i c i S \ T e c(e) e S ( ) T {e S } e T \ T c(e) e T ( ) 4.3 ( ) T = (T {e S }) \ {e T } c S T < S T T T T T G M (G) T 4.4. G = (V, E) c 1,..., c k : E R + well-defined T E R. T T 1 λ T = λ T = (1, 0, 0,..., 0) R T < R T R 2 T = T 0, T = T 1 T j T j+1 T S T j S j λ Tj (1, 0, 0,..., 0) 8

9 j j > j λ Tj λ Tj λ Tj = (1, 0, 0,..., 0) 1 j λ Tj+1 λ Tj λ Tj+1 = λ Tj S j S j+1 λ Tj+1 λ Tj S j = S j+1 j S j T j+1 < S j T j S j = S j+1 = S j+2 = j > j λ Tj λ Tj 4.5. MC-MCST T G M (G) T MC-MCST λ 5 [4] Ax b, x 0 ( A R m n b R m ) c R n x c x 1 k c 1,..., c k : MC-LP : A R m n, b R m, c 1,..., c k R n : c 1,..., c k Ax b, x 0 x MC-MCST 9

10 MC-LP n n MC-LP MC-LP 6 [5]. MC-MCST 1 ( ) ( ) 4.2 λ T Emo Welzl [1] D. Avis and K. Fukuda, Reverse search for enumeration. Discrete Applied Mathematics 65 (1996) [2] M. Ehrgott, On matroids with multiple objectives. Optimization 38 (1996)

11 [3] M. Ehrgott, Multicriteria Optimization (Second Edition). Springer, Berlin Heidelberg, [4] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization (2nd Corrected Edition). Springer-Verlag, Berlin New York, [5] V. Kaibel and M. Pfetsch, Some algorithmic problems in polytope theory. In: Algebra, Geometry, and Software Systems, M. Joswig and N. Takayama, eds., Springer-Verlag, 2003, [6] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, (3rd Edition). Springer, Berlin, [7] C. Papadimitriou and M. Yannakakis, On the approximability of trade-offs and optimal access of web sources. Proc. 41st FOCS (2000) [8] E.L. Ulungu and J. Teghem, The two phase method: An efficient procedure to solve biobjective combinatorial optimization problems. Foundations of Computing and Decision Sciences 20 (1995) [9] D.B. West, Introduction to Graph Theory (Second Edition). Prentice Hall, Upper Saddle River, [10] C. Zaroliagis: Recent advances in multiobjective optimization. Proc. 3rd SAGA (2005) [11] E. Zitzler, M. Laumanns, and S. Bleuler, A tutorial on evolutionary multiobjective optimization. In: X. Gandibleux, M. Sevaux, K. Sörensen, V. T kindt, eds., Metaheuristics for Multiobjective Optimisation, Lecture Notes in Economics and Mathematical Systems 535 (2004) pp

i Version 1.1, (2012/02/22 24),.,..,.,,. R-space,, ( R- space),, Kahler (Kähler C-space)., R-space,., R-space, Hermite,.

R-space ( ) Version 1.1 (2012/02/29) i Version 1.1, (2012/02/22 24),.,..,.,,. R-space,, ( R- space),, Kahler (Kähler C-space)., R-space,., R-space, Hermite,. ii 1 Lie 1 1.1 Killing................................