左順序付き柔軟らべリングの実装

Classifying Customer-Provider
Relationships in the Internet
Thomas Erlebach,Alexander Hall
Computer Engineering and Networks Lab.,ETH Zűrich
Thomas Schank
Dep.of Computer & Information Science,Universität Konstanz
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
1
[email protected]から
中村先生（[email protected]）にメールを送信する場合では
jp
ac
us
AS
AS
peer
peer
tohoku
is
dais
edu
berkeley
riec
stanford
umunhum
AS
customer
AS
provider
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
2
Preliminaries
Given a simple,undirected graph G=(V,E) and a set P of
simple ,undirected paths in G.
Definition 1 :
For a classifica tion, a path p   is valid
•if it starts with zero or more customer-provider
edges
•followed by zero or one peer-peer edge
•followed by zero or more provider-customer
edges
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
3
Examples
pa :
pb :
pc :
pd :
pe :
pf :
×
×
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
4
Lemma 2
for a given edge classification ,
p  P is vaild 
no source node in it
×
peer-peer edges can be completely disregarded.
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
5
The problems in this paper
Type-of-Relationship problem(ToR)
given a graph G=(V,E) and a set P of simple,undirected paths in G,classifying the
edges of the graph into customer-provider relationships such that as many of
the paths in P as possible are valid.
ALLToR
decide
orientatio n of G s.t. pi  P are valid,and
compute it if it exists.
MAXToR
compute an orientation of G s.t.
max( k ) , k  { pi  P is valid }
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
6
The ALLToR Problem
---------solve ALLToR in linear time by reducing it to 2SAT
Lemma 3:
① p  P of length k can be split up into k-1 paths pi , 1  i  k 1 of length 2 and
② orientatio n Of G , p is valid
all pi are valid.
p : e1 v e2
p1 : e1 e2
e2
p2 :

e3
e3
directed path p1
e1
e2
Note:edge ei appears negated if it is
pointing away from the internal node v of
path p and not negated if it is pointing
towards v
e1 e2 p1 valid 2SAT clause
in
in
in out
out in
out out
yes
yes
yes
no
e1  e2
e1  e2
e1  e2
e1  e2
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
7
The ALLToR Problem
SAT problem
variables:
x1, x2 , ......xn
clauses:
C1,C2 , ......Cm
---------what is 2SAT problem
a literal is a variable or the negation of a variable and a clause
is a set of literals. A clause is true is one of the literals in the
clause is true.
the input to SAT is a collection of clauses
the output is the answer to: Is there an assignment of true/false
to the variables so that every clause is satisfied (satisfied
means the clause is true)?
when all clauses Ci  2,1  i  m ,we call it 2SAT problem.
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
8
The ALLToR Problem
---------solve ALLToR in linear time by reducing it to 2SAT
1.Orient the edges of G=(V,E) arbitrarily.
2.Split all paths p   into  ( p) -1paths of length 2,where ( p) is the
length of path p .
pP
3.Construct a 2SAT instance where each edge ei  E corresponds to a
variable and each path p (of length 2) corresponds to a clause .
4.Solve the resulting 2SAT instance.
5. If the 2SAT instance is not satisfiablethe ALLToR is not solvable.

otherwise,flip ei  E :whose corresponding variable has been
assigned false by 2SAT
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
9
The MAXToR Problem
---------prove that MAXToR is NP-hard
To prove that MAXToR is NP-hard,we wil give an
reduction from the well known NP-hard maximum
independent set problem(MAXIS) to MAXToR.
Lemma 4
G  (V , E ) with two paths s.t.同時にvalidできない
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
10
The MAXToR Problem
---------prove that MAXToR is NP-hard
What is MAXIS problem?
・INSTANCE: Graph G  (V , E.)
・SOLUTION: An independent set of vertices V '  V
s.t. vi , v j V 'arenot joined by an edge
max( V )
'
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
11
The MAXToR Problem
---------prove that MAXToR is NP-hard
MAXISのinstance H  (VH , EH )からMAXToRのinstance (G , P )を作る
vi  pi , vi VH , pi  P
s.t. pi , p j  P
・ vi , v j  E H ー> piと p j はedge-disjoint.
・ vi , v j  E H ー> pi と p j は同時にvalidにしないように。
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
12
The MAXToR Problem
---------conclusion
もしMAXToRは多項式時間で解ける或いは近似解を求められ
るならば、MAXISに対しても同じことを言える。
しかし、MAXISはNP-困難である、そして任意の   0に対し
て近似率は 1 n1の近似アルゴリズムは存在しないことは既に
知られている。
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
13
Approximating MAXToR instances
with bounded path length
a simple approximation algorithm
各edgeに対して勝手に方向をつける。
p1 :
p2 :
a path of length k is valid with
probability k  1
2k
pk 1 :
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
14
Approximating MAXToR instances
with bounded path length
pi  P, ( pi )  k , ( pi ) : the length of piならば
E(A rand ) 
k 1
k 1
n

Opt ,
k
k
2
2
A rand：近似解、 Opt：最適解
the most length of paths approximatio ratio
2
0.75
3
0.5
4
0.3125
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
15
Approximating MAXToR instances
with bounded path length
MAX2SATを用い、もっと良い近似率を得られる。
帰着
方針：
MAXToR
符号の定義：
 MAX 2 SAT
Opt : MAXToRの最適解
AK : MAXToRの近似解
g k  P ' , P '  P, pi  P ' : ( pi )  k
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
16
Approximating MAXToR instances
with bounded path length
①パスの長さ＝２のとき，
p : e1 e2
 

節　C   1   2 ,  1  e1, e1 ,  2  e2 , e2

Cを充足できる  pはvalid
MAXToRの近似率＝0.931(MAX2SATの近似率)
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
17
Approximating MAXToR instances
with bounded path length
②パスの長さ＝３のとき，
e1 e2 e3
p:
p2 : e2 e3
p1 : e1 e2
C1  1   2 ,
, 1  e1 , e1 ,  2  e2 , e2 ,  3  e3 , e3
C2   2   3,
 




C1と C2を同時に充足できる  pはvalid
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
18
Approximating MAXToR instances
with bounded path length
②パスの長さ＝３のとき，
MAXToRの最適解は Opt  MAX 2SATの最適解は Opt  g3
同様に
MAXToRの近似解は A3  MAX 2SATの近似解は A3  g3
A3  g 3
既存研究によって Opt  g  r , r  0.931
3
A3  0.818Opt
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
19
Approximating MAXToR instances
with bounded path length
③パスの長さ＝４のとき，
②の場合と同じ方法で評価する
A4  0.352Opt
④パスの長さ＞４のとき，以上の方法は助からない。
 MAX 2SATの解は常に
３
の節を充足できる
４
pi  Pはvalidでない可能性がある
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
20
Approximating MAXToR instances
with bounded path length
最大パス長ランダム近似algo. MAX2SATを用いる近似algo.
2
0.75
0.931
3
0.5
0.818
4
0.3125
0.352
k 1
k 1
>4
2
2
k
k
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
21
MAXToRはAPX-完全
・すべてのパス長＝２の場合でも、MAXToRはある定数を超える近似率を
得られない。
方針：
MAX 2SATのinstance から MAXToR のinstance( G, P)を作る。
MAX 2SATのinstance :

変数xi , i  1....n '






節ck   i   j ,  i  xi , xi ,  j  x j , x j , k  1....m '

TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
22
MAXToRはAPX-完全
．xiに対してノード
 
xi , xiと edge ei  xi , xi
Gに加える。
．ck   i   jに対して edge ek   i ,  j を Gに加える。
． path pk  ( i ei  i ek  j e j  j )を Pに加える。
作られたMAXToRのinstanceの解に対して、
pkはvalid  ckは充足
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
23
MAXToRはAPX-完全
パス長＝２の場合に対応するため、
pk  ( i ei  i ek  j e j  j )
pk  ( i ei  i ek  j )
'
pk ' '  ( i ek  j e j  j )
ckは充足  pkと pk はvalid
'
''
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
24
MAXToRはAPX-完全
MAXToRの最適解は Opt  MAX 2SATの最適解は Opt  m'
同様に
MAXToRの近似解は A2  MAX 2SATの近似解は A2  m'
既存研究によって
A2  m'
 q, q  0.955
'
Opt  m
A2  0.980Opt
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
25

Download Report