Database Reference
In-Depth Information
Final winner:
c
N1
h
c
N2
N3
f
b
c
h
N4
N5
N6
N7
g
ab
c
d
f
h
Fig. 4.3
Computing the approximate second most typical instance.
Proof.
For any instance
x
∈
C
,
1
∑
∑
(
,
)=
G
h
(
,
)+
G
h
(
,
)
T
x
O
x
y
x
z
|
S
|
h
y
∈
LN
(
C
,
S
,
σ )
z
∈
(
S
−
LN
(
C
,
O
,
σ ))
1
Since
LT
(
x
,
C
,
O
,
σ)=
,
σ )
|
∑
y
∈
LN
(
C
,
O
,
σ )
G
h
(
x
,
y
)
,
h
|
LN
(
C
,
O
|
(4.4)
1
∑
T
(
x
,
O
)=
LN
(
C
,
O
,
σ )
|·
LT
(
x
,
C
,
O
,
σ)+
G
h
(
x
,
z
)
h
|
O
|
z
∈
(
O
−
LN
(
C
,
O
,
σ ))
O
,
|
LN
(
C
,
O
,
σ )
|
|
Because
LN
(
C
,
O
,
σ )
⊆
|
≤
1. Thus,
O
1
∑
T
(
x
,
O
)
≤
LT
(
x
,
C
,
O
,
σ)+
G
h
(
x
,
z
)
(4.5)
h
|
O
|
z
∈
(
O
−
LN
(
C
,
O
,
σ ))
According to the definition of local neighborhood,
d
(
x
,
z
)
>
σ
for any
z
∈
(
O
−
LN
(
C
,
O
,
σ ))
. Thus,
1
1
√
2
e
−
σ
2
∑
G
h
(
x
,
y
)
<
(4.6)
2
h
2
|
O
|
π
y
∈
(
O
−
LN
(
C
,
O
,
σ ))
Inequality 4.3 follows from Inequalities 4.5 and 4.6 immediately. Applying Equa-
tion 4.4 to
o
and
o
, respectively, we have
)=
|
LN
(
C
,
O
,
σ )
|
|
T
(
o
,
O
)
−
T
(
o
,
O
(
LT
(
o
,
C
,
O
,
σ )
−
LT
(
o
,
C
,
O
,
σ ))
O
|
1
+
|
∑
z
∈
(
O
−
LN
(
C
,
O
,
σ ))
(
G
h
(
o
,
z
)
−
G
h
(
o
,
z
))
h
|
O
Using Inequality 4.6, we have
