traveling salesman, min set cover

Approximate Salesman traveling  salesman  (tsp)

Input:  \(A_{n}\)  n × n  matrix  \(d_{ij}\)  ≥  0
Output: A cyclic permutation π that minimizes \(\ c(\pi ) = \sum_{i=1}^{n}d_{i, \pi (i)}\)

π  :  {1, · · · , n}  →  {1, · · · , n}  is  a  permutation  where  π(i)  denotes  i’s successor.

 

traveling  salesman  (threshold)
Input:  \(A_{n}\)  n × n  matrix  \(d_{ij}\)  ≥  0  and  a  number  l
Question:   Is  there  a  cyclic  permutation  π  such  that  c(π)  ≤  l?

By  reducing  Hamiltonian  cycle  to  tsp  (threshold),  we  prove  that  tsp is  NP-hard.

 

해밀턴 순환을 tsp (threshold) 으로 감축하여 tsp 가 더 어려운 문제 즉, NP-hard 임을 증명해보도록 하자.

 

Given  an  graph  G  =  (V, E)  with  n  vertices,  define  an  instance  of tsp  as  \(d_{ij}\)   =  1  

if  (i, j)  ∈  E   and  \(d_{ij}\)  =  100  if  (i, j)  \(\notin\)  E.
Then,  G  has  a  Hamiltonian  cycle  if  and  only  if  the  corresponding tsp  has  a  tour  of  cost  n.
If  G  is  not  Hamiltonian,  the  shortest  tour  has  length  ≥  n + 99. 

⇒  tsp  (threshold)  is  NP-complete  and  tsp  is  NP-hard.

 

그래프 G가 주어질 때, (i, j) 의 간선이 연결될 경우 \(d_{ij}\)  =  1, 연결되지 않을 경우 \(d_{ij}\)  =  100 으로 정의한다.

G는 tsp가 n의 비용으로 투어할 경우 해밀턴 순환이라고 할 수 있다. (그래프 G는 n개의 정점이므로)

G가 해밀턴 순환이 존재하지 않을 경우 적어도 투어할 수 있는 길이는 n + 99 보다 크거나 같은 경우다.

 

예를 들어서 다음과 같은 경우를 고려해보자

(1) 1 => 2 => ... => n 정점까지 정상적으로 도착할 경우 n - 1 의 길이만큼 투어를 한다.

(2) n => 1 로 가는 경로가 존재하지 않는다면 결국 해밀턴 경로가 존재하지 않으므로 100 의 길이만큼 투어를 한다.

(3) 따라서 (n - 1) + 100 = n + 99 가 최소의 투어 길이가 된다.

 

따라서 tsp(threshold)는 NP-complete 이며 tsp는 NP-hard가 된다.

How  about  an  approximation  algorithm  for  tsp?
If we define \(d_{ij}\) = 1 if (i, j) ∈ E and \(d_{ij}\) = 1 + ρn, ρ > 0, if (i, j)  \(\notin\)  E, then the length of the shortest tour is n if G is Hamiltonian and ≥ (1 + ρ)n if it isn’t.

If  we  had  a  (1 + ρ′)-approximation  algorithm  for  tsp  for  ρ′  <  ρ,  we could  distinguish  the  two  cases  and  therefore  solve  Hamiltonian cycle  in  polynomial  time!

 

위에서 적용한 방식으로 \(d_{ij}\) = 1 일 경우 (i, j) 의 간선이 연결되어 있고 \(d_{ij}\) = 1 + ρn 일 경우 (i, j) 의 간선이 연결되지 않은 경우라고 하자.

해밀턴 순환이 존재하지 않을 경우 (n - 1) + (1 + ρn) = (1 + ρ)n 로 최소 투어 길이가 된다.

 

ρ′  <  ρ 에 대한 tsp의 (1 + ρ′)-approximation algorithm 을 얻게 된다면, 해밀턴 사이클을 polynomial time 에

해결할 수 있게 된다.

 

We  say  dij    form  a  metric if  \(d_{ij}\)  =  \(d_{ji}\) ,  i.e.,  symmetric,  and  obey  the triangle  inequality:  \(d_{ij}\)  ≤  \(d_{ik}\) + \(d_{kj}\)  for  all  i, j, k.
We  call  tsp  in  which  distance  forms  a  metric  metric  tsp  or  △  tsp. 

 

A  metric  example  is  the  Euclidean  distance  in  the  plane  where  the  distance  between  (xi , yi )  and  (xj , yj )  is  \(d_{ij}\) = \(\sqrt{\left ( x_{i}-x_{j} \right )^{2} + \left ( y_{i}-y_{j} \right )^{2}}\)  tsp  with  Euclidean  distance  is  called  Euclidean  tsp.

It  can  be  shown  that  both  △  tsp  and  Euclidean  tsp  are  NP-hard. 

 

△  tsp 와 Euclidean tsp 둘 다 NP-hard NP-hard 임을 보일 수 있다.

 

We  now  give  a  2-approximation  algorithm  for  △  tsp.

We  make  use  of  the  fact  that  Eulerian  cycle,  i.e.,  one  that  traverses each  edge  exactly  once,  can  be  changed  to  a  Hamiltonian  one simply  by  skipping  vertices  that  have  been  visited.
If  triangle  inequality  holds,  this  never  increases  the  length  of  the cycle.   

E.g., if  we  already  visited  k,  skipping  directly  from i to j incurs  cost  \(d_{ij}\) ≤ \(d_{ik}\) + \(d_{kj}\).   

 

우리는 오일러 순환, 즉 각 모서리를 정확히 한 번 가로지르는 순환이 방문한 정점을 건너뛰기만 하면 해밀턴 순환으로 바뀔 수 있다는 사실을 이용한다.
만약 삼각 부등식이 유지된다면, 순환의 길이를 늘리지 않는다.

예를 들어, 이미 k를 방문한 경우 i에서 j로 바로 건너뛰는 경우에 \(d_{ij}\)≤\(d_{ik}\)+\(d_{kj}\) 를 만족한다.

이를 만족하는지 다음 그림을 통해 살펴보도록 한다.

 

 

먼저 스패닝 트리 (A) 가 있다고 할 때, 임의의 정점 a, b 에 대해서 a => b, b => a 에 대한 간선을 형성해 주도록 한다.

즉 모든 간선들을 2배로 형성하여 오일러 순환 (B) 가 형성되고 정점 f 에서 시작한다고 하자.

(1) f => i : \(d_{fi}\) 를 추가한다.

(2) i => f => d : 이때 f를 방문했으므로 skip 하여 d로 방문한다.

      \(d_{id}\) =  \(d_{if}\) +  \(d_{fd}\) 으로 삼각 부등식을 만족한다.

 

이런 식으로 정점 f 에서 시작하여 방문한 정점을 skip 하여 다시 정점 f 로 돌아올 경우 형성된 경로를 해밀턴 순환이라고 한다. 

Now,  first  find  the  minimum  spanning  tree  for  all  the  cities  and denote  it  by  T  and  the  total  length  of  its  edges  by  l(T).
T   may  have  vertices  of  odd  degree,  so  “Eulerify”  it  by  doubling  the edges.  (Recall,  if  all  vertices  have  even  degree,  then  it  has  an Eulerian  cycle.)
The  resulting  Eulerian  spanning  graph  has  total  length  2l(T).

 

모든 도시에 대한 최소 스패닝 트리를 먼저 정하고 그것을 T로 나타내며 간선의 총 길이는 l(T)로 표시한다.
T는 홀수의 꼭짓점을 가질 수 있으므로 모서리를 두 배로 늘려서 "Eulerify"한다.

이때 모든 꼭짓점들의 차수가 짝수를 가지면, 오일러 순환을 가지게 된다.
결과적으로 오일러 스패닝 그래프의 총 길이는 2l(T) 가 된다.

 

Skip  vertices  that  were  already  visited  in  the  Eulerian  spanning graph.   

This  gives  tour  of  length  l  ≤  2l(T).

On the other hand, if we remove an edge from the optimal tour, we get a spanning tree consisting  of a path of n − 1 edges whose length is ≥ l(T) and ≤ \(l_{opt}\), the length of the optimal tour.
This  gives  l(T) ≤  \(l_{opt}\).   

Combining  the  two  gives  l  ≤  2\(l_{opt}\).

 

오일러 스패닝 그래프에서 이미 방문한 정점을 건너뛰므로 투어 길이가 2l(T) 보다 작거나 같다.
반면에 optimal tour 에서 간선을 제거하면, 길이가  l(T) 이상이면서 \(l_{opt}\) 이하인 n - 1 간선의 경로로 구성된 스패닝 트리를 얻을 수 있다.
이를 통해 l(T) 는 \(l_{opt}\) 보다 작거나 같으며 둘을 결합하면 2\(l_{opt}\) 보다 작거나 같음을 얻는다.

ρ  =  2  came  from  “doubling”  all  edges  of  the  minimum  spanning tree.   

A  closer  look  at  the  described  approximation  scheme  reveals that  only  the  odd-degree  vertices  need  be  made  even-degree  to make  the  graph  Eulerian.

Recall  there  are  an  even  number  of  odd-degree  vertices  in  any graph,  and  so  we  can  connect  these  odd-degree  vertices  in  pairs according  to  a  perfect  matching.

 

ρ = 2는 최소 스패닝 트리의 모든 간선들을 두배로 확장하여 만들었다.

설명된 근사 체계를 자세히 살펴보면 오일러 그래프로 만들기 위해 홀수 꼭짓점들만 차수를 짝수로 만들면 된다는 것을 알 수 있다.

 

We  again  start  with  the  minimum  spanning  tree  T.
Let  U   denote  the  set  of  vertices  that  have  odd  degree  in  T  and  let  M  be  the  minimum-length  perfect  matching  on  U . (This  can  be found  in  polynomial  time.)

Then  take  an  Eulerian  tour  of  T ∪ M   skipping  cities  already  visited  giving  the  total  length  of  the  tour  l  ≤  l(T) + l(M).

 

다시 초심으로 돌아가서... 최소 신장 트리 T로 다시 시작해보도록 한다.
U : T에서 홀수 차수를 가지는 정점들의 집합으로 정의

M : U에서 최소 길이의 완전 매칭으로 정의

그 후에 l(T) + l(M) 이하의 투어의 총 길이를 가진채로 T ∪ M 에 대한 오일러 경로에서 이미 방문한 도시들은 skip 함으로써 오일러 투어를 하도록 한다. 

 

 

위 사진을 보면 스패닝 트리 (A) 에서 정점들 중에 차수가 홀수인 정점들을 구한다. 

차수가 홀수인 정점들을 차수가 짝수가 되도록 만들면 (B) 와 같은 그래프가 형성된다. 

 

 

(B) 그래프에서 새로 추가된 간선들은 위에서 언급한 M 이라고 볼 수 있겠다. (U는 홀수 차수인 정점들 집합)

그 후에 오일러 투어를 함으로써 방문한 정점들을 skip 하면서 해밀턴 순환 (C) 를 형성하게 된다.

 

Clearly,  l(T)  ≤  \(l_{opt}\).

 

Claim : l(M) ≤  \(l_{opt}\)/2.    ( => l  ≤  \(\frac{3}{2}l_{opt}\))

 

홀수 차수인 정점들의 집합 U 에서 서로 연결만 시켜준다면 짝수 차수를 형성할 수 있다.

따라서 자연스럽게 Claim 에 대한 부등식을 이해할 수 있겠다.

Consider a salesman who only has to visit the cities in U.

He can do this by following the optimal tour but skipping the other cities.

By the triangle inequality, the resulting tour has length \(l_{U}\) ≤ \(l_{opt}\).

 

오직 U에 있는 도시들을 방문하기만 하면 되는 세일즈맨을 생각해보자.

그는 최적의 투어를 따르지만 다른 도시들은 건너뛰는 것도 할 수 있다.

따라서 삼각 부등식에 의해 결과 투어의 길이는 \(l_{U}\) ≤ \(l_{opt}\) 이다.

 

This  tour  contains  two  perfect  matchings  \(M_{1}\), \(M_{2}\) on
U   =  {\(u_{1}\), · · · , \(u_{t}\)}  whose  vertices  are  numbered  according  to  their order  in  this  tour.

    M1   =   {(\(u_{1}\), \(u_{2}\)), (\(u_{3}\), \(u_{4}\)), · · · , (\(u_{t-1}\), \(u_{t}\))} 

M2   =   {(\(u_{2}\), \(u_{3}\)), (\(u_{4}\), \(u_{5}\)), · · · , (\(u_{t}\), \(u_{1}\))} 

But  l(\(M_{1}\)) + l(\(M_{2}\))  =  \(l_{U}\)  ≤  \(l_{opt}\).
So  either  l(\(M_{1}\))  ≤  \(l_{opt}\)/2  or  l(\(M_{2}\))  ≤  \(l_{opt}\)/2.   

In  either  case,  the minimum-length  perfect  matching  on  U  has  length  ≤  \(l_{opt}\)/2.

This  is  the  best  known  approximation  algorithm  for  △  tsp.
If  we  restrict  to  Euclidean  tsp,  we  can  get  a  (1 + ε)-approximation  in polynomial-time  for  any  fixed  ε  >  0,  i.e.,  a  PTAS.

 

l(M) ≤  \(l_{opt}\)/2 에 대한 확인을 하였다.

지금까지 본 것은 △ tsp에 대해 가장 잘 알려진 근사 알고리즘이다.
만약 유클리드 tsp로 제한한다면, 우리는 어떠한 ε > 0 으로 다항식 시간에 (1 + ε) 근사치를 얻을 수 있다.

 

 

min  set  cover

Input:   A  family  of  subsets  S1, · · · , Sl   ⊆  {1, · · · , m}. 

Output:   The  smallest  subset  A  ⊆  {1, · · · , l}  s.t.

 

\(\bigcup_{i\in A}^{}S_{i} \) = {1, · · ·, m} ?

Aka  recruiting  a  team:   There  is  a  set  of  m  skills  that  we  need  to have,  and  each  person  i  has  a  set  of  skills  \(S_{i}\).   

The  problem  is  then to  find  the  smallest  team  that  covers  all  m  skills.

Note  that  vertex  cover  is  the  case  where  skills  are  edges,  people  are vertices,  and  each  skill  is  possessed  by  exactly  two  people.

So,  vertex  cover  ≤  set  cover.

 

Aka의 팀 모집으로 우리가 갖춰야 할 m개의 스킬 세트가 있고, 각각의 사람 i에 대해서 \(S_{i}\) 기술들의 세트를 가지고 있다.
문제는 모든 m개의 스킬들을 다루는 가장 작은 팀을 찾아야 하는 것이다.
꼭짓점 덮개는 스킬들이 간선이고, 사람이 꼭짓점이며, 각각의 스킬은 정확히 두 사람이 소유하는 경우이다.
따라서, vertex cover 를 set cover 로 감축할 수 있다.

 

Try  a  greedy  strategy  by  adding  people  to  the  team  one  at  a  time,  at  each  step  adding  the  one  that  covers  the  largest  number  of additional  skills.

Start  with  A  =  ∅  and  at  each  step  update  A  to  A′   =  A ∪ {j}  where j  maximizes  the  number  of  newly  covered  elements

 

|\(S_{j}-\bigcup_{i\in A}^{}S_{i}\)|

Claim:   This  strategy  achieves  an  approximation  ratio  ρ  ≤  log m.

 

각 단계에서 한 번에 한 명씩 팀에 사람을 추가하는 그리디한 전략을 시도해보자.
A = ∅로 시작하여 각 단계에서 A를 A′   =  A ∪ {j} 으로 업데이트 한다. (j는 새로 적용된 요소의 수를 최대화함)
이러한 전략은 근사 비율 ρ ≤ log m 을 달성한다.

이에 대해서 살펴보도록 하자.

 

Let  \(u_{t}\)  denote  the  number  of  uncovered  elements  just  after  the greedy  algorithm  has  taken  its  \(t^{th}\)  step,  i.e.,

 

\(u_{t}\) = m - |\(\bigcup_{i=1}^{t}S_{i}\)|.

Supppose  the  optimal  cover  has  size  k  (>  t).   

So  \(u_{t}\)  elements  remain uncovered  and  ≥  (k  − t)  sets  will  be  added  to  cover  all  elements.

From  the  optimal  cover,  k  − t,  k  − t + 1,  · · ·,  or  k  sets  may  be added  to  cover  all  elements.
In  other  words,  there  must  be  some  set  S   in  the  optimal  cover,  not yet  taken  by  the  greedy  algorithm,  which  covers  at  least  \(\frac{u_{t}}{k}\)  of  these  elements.

 

그리디 알고리즘이 t번째 단계를 밟은 직후에 드러나지 않은 원소(스킬들)의 수를 \(u_{t}\)로 나타낸다.
최적의 덮개 크기가 k (> t)라고 가정할 때, \(u_{t}\) 원소는 여전히 덮이지 않은 상태로 남아 있고 (k - t) 이상의 집합들은 모든 원소를 덮기 위해 추가될 것이다.

최적의 커버에서 k - t, k - t + 1, · · 또는 k 세트를 추가하여 모든 원소들을 커버할 수 있다.
즉, 최적의 덮개 안에 적어도 \(\frac{u_{t}}{k}\) 개의 요소를 포함하는 그리디 알고리즘에 의해 아직 차지하지 않은 S 집합이 있어야 한다.

 

So  the  next  step  of  the  greedy  algorithm  reduces  the  number  of uncovered  elements  to

 

\(u_{t+1}\)  ≤  \(u_{t}\) - \(\frac{u_{t}}{k}\) = (1 - \(\frac{1}{k}\))\(u_{t}\)

 

we have \(u_{0}\) = m, and so

 

\(u_{t+1}\)  ≤  \(m\left ( 1-\frac{1}{k} \right )^{t}\)  <   \(me^{-\frac{t}{k}}\) 

where  (a)  follows  from  \(e^{x}\)  =  1  +  x  +  \(\frac{x^{2}}{2!}\)  +  \(\frac{x^{3}}{3!}\)  +  · · ·.

The  algorithm  stops  as  soon  as  \(u_{t}\)  =  0  at  which  point  it  has produced  a  cover  of  size  t.

Since  \(u_{t}\)  is  an  integer,  we  can  say  it  stops  as  soon  as  \(u_{t}\)  <  1.

We  have  shown  this  happens  before  t  =  k log m.

 

그래서 그리디 알고리즘의 다음 단계는 드러나지 않은 원소의 수를 위와 같이 줄인다.

알고리즘은 크기가 t 인 덮개를 생성한 시점에  \(u_{t}\) = 0이 되는 즉시 중지된다.
 \(u_{t}\)는 정수이기 때문에, \(u_{t}\) < 1 만큼만 정지한다고 말할 수 있다.
따라서 t = k log m 이전에 발생한다는 것을 보일 수 있다.