Optimization and Approximation

We  explore  the  relationship  between  decision problems  and  their  optimization  versions.
For  most,  the  optimal  solution  can  be  found  in  polynomial  time  if and  only  if  the  decision  

version  can  be  also.

 

이번에 배울 내용은 decision problem과 optimization version 사이의 관계를 알아가는 부분이다.

optimal solution은 decision version이 polynomial time에 속하게 될 경우 발견된다고 한다.

 

 

For  computationally  intractable  problems,  we  will  study approximation algorithms.
Some  problems  allow  approximations  to  get  arbitrarily  close  to  the optimum  while  others  do  not.

 

어떤 문제는 근사치가 임의로 최적에 근접할 수 있는 반면 다른 문제는 그렇지 않는다.

 

Lastly,  we  look  at  a  family  of  optimization  problems,  called  linear programming,  that  can  be  

solved  in  polynomial  time.
Here,  we  try  to  maximize  a  function  subject  to  a  set  of  constraints.

 

Linear  programming  comes  in  pairs  (“duality”)  in  which  variables  of  one  problem  

correspond  to  the  constraints  of  the  other. 

E.g.,  max  flow  and  min  cut.

 

마지막으로, 다항식 시간 내에 해결할 수 있는 선형 프로그래밍이라는 최적화 문제군을 살펴본다.
여기서는 일련의 제약 조건에 따라 함수를 최대화하려고 한다다.
선형 프로그래밍은 한 문제의 변수가 다른 문제의 제약과 일치하는 쌍("duality")으로 나타난다.

 

 

Three Flavors of Optimization 

 

max-sat  (optimization)
Input:   A  sat  formula  φ
Output:   A  truth  assignment  that  satisfies  as  many  of  φ’s  clauses  as possible

max-sat  (value) 

Input:   A  sat  formula  φ
Output:   The  largest  l  of  clauses  that  can  be  satisfied  at  once 

 

max-sat  (threshold)
Input:   A  sat  formula  φ  and  an  integer  l
Question:   Is  there  a  truth  assignment  that  satisfies  l  or  more clauses  in  φ?

 

optimization, value, threshold 에 대한 max-sat 에 대해서 살펴보려고 한다.

optimization : 가능한 많은 clauses 를 만족시키도록 하는 진리표를 찾는 것이다.

value : 한번에 충족될 수 있는 clauses 들의 최대 l 을 찾는 것이다.

threshold : l 또는 그 이상의 clause 들을 충족시키는 진리표를 찾는 것이다.

 

Observe  that
max-sat  (threshold)  ≤  max-sat  (optimization),  max-sat  (value). 

Since  max-sat  (threshold)  is  NP-complete,  

we  can  reduce  any problem  in  NP  to  the  other  two  versions  also.

 

먼저 max-sat (threshold) 는 NP-complete 에 속하기 때문에 optimization, value 에 대한 max-sat

으로 감축할 수 있다.

Problems  with  this  property  are  called  NP-hard.   

I.e.,  they  are  at least  as  hard  as  any  problem  in  NP  and  possibly  harder.
E.g.,  optimization  versions  of  independent  set,  vertex  cover,  max  cut are  all  NP-hard.

 

결국 NP-complete 문제에서 reduction 을 했으므로 해당 문제보다 더 어려운 것은 사실이다.

즉, 이러한 속성을 가진 문제들을 NP-hard 라고 부르며 NP 보다 더 어려운 문제로 불린다.

independent set, vertex cover, max cut 을 optimization 한 버젼들 전부 NP-hard 라고 부른다.

Suppose  now  an  oracle  ∃  that  can  solve  the  threshold  problem.

If  φ  has  m  clauses,  the  largest  number  of  clauses  we  can  possibly satisfy  is  m.
We  can  solve  max-sat  (value)  through  binary  search  using  log2(m) calls  to  the  oracle.

 

임계 문제를 해결할 수 있는 oracle이 있다고 가정해보자.

m개의 항들을 보유한다고 할 때, φ 를 충족시킬 수 있는 항들의 가장 큰 숫자를 m 이다. 

따라서 max-sat (value)에 대한 문제는 oracle 에 대한 log2(m) 을 사용하는 이진 탐색을 통해 해결할 수 있다.

 

 

Assuming  we  can  solve  max-sat  (value),  what  can  be  said  about max-sat  (optimization)?
Given  a  sat  formula  φ(x1, · · · , xn ),  setting  x1 “true”  or  “false” satisfies  some  of  φ’s  clauses  

and  shortens  others.

 

max-sat (value) 를 해결할 수 있다고 가정할 때, optimization 에 대한 max-sat 에 대해서 어떻게 해결할 지에

대한 문제이다.

sat formula φ 가 주어지면 φ의 몇 가지 항들을 만족시키는 x1을 "true"나 "false"로 먼저 설정하고 다른 항들을

단축시킨다.  

This  yields  a  sat  formula  on  the  remaining  variables,  φ ′  =  φ[x1 →  true]  or  φ′   =  φ[x1 →  false], 

and  one  of  these  two  leads to  the  optimal  assignment.

We  can  assign  x1 the  truth  value  s.t.   opt(φ′ )  =  opt(φ),  and  repeat   this  procedure  until 

we  assign  value  to  xn .

 

이렇게 하면 나머지 변수로 φ' = φ[x1 → true] 또는 φ' = φ[x1 → false] 에 대한 sat formula 를 생성하며

둘 중 하나가 최적의 할당으로 이어지게 된다.
즉 x1를 위 식과 같이 할당할 수 있으며 xn의 값을 할당할 때까지 이 절차를 반복한다.

 

여기서 주의해야 할 점은 값이 커지는 경우는 formula 를 만족시키지 않는 점을 알아두자.

예를 들어서 (x1, x2, x3) = (0, 0, 1) 는 x1와 x2가 0, 0 이라는 점에서 첫번째 항에서 false 이기 때문에 false 이다.

즉, 최적의 값이 지속적으로 해당 formula의 cluase의 갯수의 값을 지속적으로 유지하게 되는 path 를 찾아가게

된다면 해당 노드들은 optimal solution 임을 알 수 있게 된다.

 

 

If  φ  has  n  variables,  then  the  total  number  of  times  we  run  the optimal  value  algorithm  is  

at  most  2n.
⇒ max-sat  (optimization)  ≤  max-sat  (value)  ≤  max-sat  (threshold)

 

n개의 변수가 존재하게 된다면 optimal value 알고리즘을 실행시키는데 필요한 총 시간은 2n 이 된다.

 

Here,  A  ≤  B   denotes  a  Turing reduction where  if  we  have  an  oracle
for  B,  we  can  solve  A  with  a  polynomial  number  of  calls  to  this oracle.

 

위에서 뭔가 이상하게 감축된 표현을 느꼇다.

여기서의 A ≤ B 는 만약 우리가 B에 대한 오라클을 가지고 있다면, 우리는 이 오라클에 대한 polynomial의 

호출 수로 A를 해결할 수 있는 Turing reduction 을 나타낸다.

For  problems  that  are  self-reducible,  i.e.,  problems  in  which assigning  a  value  to  

a  variable  leads  to  the  same  problem  on  the remaining  variables,  determination  of  the  value 

problem  yields  solution  to  the  optimization  problem.

Most  optimization  problems  such  as  max-sat  are  self-reducible.

자기 자신을 축소 가능한 문제들로 값 문제의 결정은 최적화 문제에 대한 해결책을 산출한다.
max-sat 과 같은 대부분의 최적화 문제는 자체 축소 가능하다.

 

 

Approximations

If  an  optimization  problem  is  NP-hard,  can’t  expect  to  find  an efficient  algorithm  that  

finds  the  optimal  solution.
Can hope for a good solution using an efficient algorithm, however. 

 

최적화 문제가 NP-hard 일 경우, 이를 해결하기 위한 최적의 해결책을 찾을 수 있는 효율적 알고리즘을 찾는

것을 기대할 수 없다는 점이다.

그러나 효율적인 알고리즘을 사용할 경우, 좋은 해결책을 바랄 수 있다는 점이 있다.

 

For an algorithm A and an instance x, let A(x) denote the quality  of  the  solution  A  produces.
Let  OPT(x)  denote  the  quality  of  the  optimal  solution.

 

알고리즘 A와 인스턴스 x의 경우 A(x)가 A가 생성하는 솔루션의 퀄리티를 나타내도록 한다.

We  say  A  is  a  ρ-approximation for  a  maximization  problem  if,  for all  instances  x,

A(x)/OPT(x)  ≥  ρ where  ρ  ≤  1.   

 

For  a  minimization  problem,  we  have

A(x)/OPT(x)  ≤  ρ where  ρ  ≥  1.

 

위에 대한 관계식은 maximization, minimization 문제에 대한 ρ-approximation 관계식이다. 

 

NP-complete  problems  are  all  equal when  trying  to  find  the optimum  value.
On  the  other  hand,  when  trying  to  approximate  the  optimum value,  

some  can  be  approximated  closely  while  others  can’t.

 

NP-complete 문제는 최적값을 구하려고 할 때 모두 같다.
반면에, 최적의 값을 근사화하려고 할 때, 어떤 것은 근접하게 근사할 수 있는 반면 어떤 것은 그렇지 않다.

즉, 최적값을 구하려고 할 때의 값은 전부 동일하지만 최적 값을 근사하려고 할 때의 값이 그렇거나 그렇지

않다는 점을 알 수 있다.

Consider  vertex  cover  and  its  variant  min  vertex  cover  which  asks  for the  smallest  

possible  vertex  cover  of  G.
Since  vertex  cover  is  NP-complete,  min  vertex  cover  is  NP-hard.   

Let us  try  to  approximate  it  by  using  pebbles  to  cover  the  vertices.

 

G의 가능한 가장 작은 min vertex cover를 요청하는 vertex cover와 그것의 변형된 vertex cover를 고려하자.
vertex cover는 NP-complete이기 때문에 min vertex cover는 NP-hard이다.
따라서 조약돌(pebble)을 사용하여 vertex 를 덮으면서 근사치를 구해보도록 한다.

Initially,  all  vertices  are  unpebbled.   

In  each  step,  choose  an  edge whose  endpoints  are both  unpebbled,  and  we  pebble  both  of  them. 

Continue  this  process  until  no  such  edge  remains,  at  which  point the  set  S   of  pebbled  

vertices  is  a  vertex  cover.

 

초기에는 모든 정점들이 조약돌(pebble)로 이루어지지 않는다.

각 단계에서 끝점이 조약돌로 덮이지 않은 edge 를 선택하면 두 vertex 에 조약돌을 둔다.
다듬어진 꼭짓점의 집합 S가 vertex cover가 될 때까지 이 과정을 계속한다.

 

사실 말로만 하면 이해가 잘 안된다. 

직접 이 과정을 그려보도록 하자.

 

 

1. 랜덤하게 간선 중 조약돌 2개가 놓이지 않은 간선을 선택하여 해당 점에 조약돌을 놓는다.

 

 

2. 1번째에서 했던 방식 그대로 조약돌이 없는 간선을 선택하여 해당 점에 조약돌을 놓는다.

 

3. 이제 더이상 간선중에 조약돌이 2개가 놓이지 않은 간선은 존재하지 않는다.

    따라서 vertex cover를 완성하였다.

 

 

Claim: S is not much larger than the optimal vertex cover Sopt . 

 

S가 최적의 vertex cover Sopt 보다 더 크지 않다고 한다.

왜 그런지 알아보도록 한다.

 

Note first that |S| = 2k where k is the number of edges that our algorithm pebbled. 

Since k edges have no vertices in common, and since each one has at least one endpoint in Sopt , 

we have |Sopt | ≥ k. 

Thus, S is at most twice as large as Sopt ,

 

여기서 k는 앞에서 사용했던 알고리즘으로 조약돌을 놓은 간선의 수이며 따라서 |S| = 2k 이다.
k개의 모서리는 공통의 꼭짓점이 없기 때문에, 그리고 각각의 꼭짓점이 Sopt 에 적어도 하나의 끝점을 가지고

있기 때문에, |Sopt | ≥ k를 가진다.
따라서, S는 최대 Sopt 의 두 배이며  ρ 값은 최소 2 값을 갖게 된다는 것을 알 수 있다. 

 

This  upper  bound  on  ρ  is  tight.   

 

 

Can  we  do  better?
The  pebble  games  achieves  ρ  =  2  by  putting  pebbles  on  both endpoints  of  any unpebbled  edge.

 

Let’s  now  put  just  one pebble  on  an  unpebbled  edge  that  will  have the  effect  of  covering  

as  many  unpebbled  edges  as  possible.

Define the degree of a vertex as the number of uncovered edges it is a part of. 

Then each step of this greedy algorithm chooses a vertex v of maximal degree and covers it.
This  type  of  algorithm  derived  from  “rule-of-thumb”  reasoning  is called  a  heuristic.

 

이제 최대한 많이 다듬어지지 않은 간선을 커버할 수 있는 다듬어지지 않은 가장자리에 조약돌 하나를

올려 놓음으로써 최대한 커버한 정점들의 갯수를 minimize 하는 방법이 도입된다.
이러한 탐욕 알고리즘의 각 단계는 최대 degree를 가진 꼭지점 v를 선택하고 그것을 덮는 방법이다.
"rule-of-thumb" 추론에서 파생된 이러한 유형의 알고리즘은 heuristic이라고 불린다.

 

그렇다면 heuristic 알고리즘을 활용한 vertex cover 를 직접 해보도록 하자.

 

 

현재 그래프에서 가장 차수가 높은 것은 5이므로 해당 점에 조약돌을 놓도록 한다.

조약돌을 놓고 나서 더이상 조약돌을 놓을 수 없는 상태가 되버린다.

만약 해당 정점이 아닌 다른 곳에 조약돌을 놓을 경우, 5개의 조약돌을 놓게 되며 당연하게도

minimization 기법에 있어서 critical 하다는 것을 볼 수 있겠다.

 

While  this  greedy  heuristic  seems  smarter  than  the  pebble  game,  it is  actually  much  worse.   

It  has  ρ  =  Θ(log n)

 

이러한 greedy heuristic은 조약돌 게임보다 더 똑똑한 것처럼 보이지만, 사실은 훨씬 더 나쁘다고 한다.
이것의 값은 ρ  =  Θ(log n) 이라고 한다.