mojo's Blog

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 permutatio..

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는 앞에서 사용했던 알고리즘으로 조약돌을 놓은 ..

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 ap..

When Maximizing is Harder than Minimizing We showed previously that min cut is in P. How about max cut? max cut Input: A weighted graph G and an integer k. Question: Does there exist a cut in G of weight k or greater? 몇주전에 min cut이 P에 속한 것을 확인하였다. (Duality, Reduction :: M - J - C (tistory.com)) max cut 은 P 에 속하는지 NP 에 속하는지에 대해서 알아보도록 한다. We will reduce nae-3-sat to unweighted max cut where every..

We have shown previously that independent set, vertex cover, and clique are all equivalent. We now show they are all NP-complete by showing independent set is. independent set이 NP-complete 임을 보임으로써 나머지 vertex cover, clique 또한 동일하게 NP-complete 임을 확인해보도록 하자. Up to now, all reductions transformed one form of constraint into another. However, independent set is not a constraint satisfaction problem ..

circuit sat Input: A Boolean circuit C Question: Is C satisfiable? Note that a Boolean circuit is a powerful enough model of computation to express any algorithm. We will show witness existence ≤ circuit sat implying circuit sat is NP-complete. We will convert an instance of (Π, x, t) of witness existence to a Boolean circuit C of polynomial size s.t. C is satisfiable if and only if there is a wit..