1. The Vertex Cover Problem
-- Input: An undirected graph G = (V , E).
-- Goal: Compute a minimum-cardinality vertex cover -- a subset S subset of V that contains at least one endpoint of each edge of G.
-- The minimum size of a vertex cover of a star graph with n verities and a clique with n vertices is 1 and n-1 respectively
-- Suppose: Given a positive integer k as input, we want to check whether or not there is a vertex cover with size <= k. Could try all possibilities, would take C(n , k) = O(n^k ) time when k is small.
2. Substructure Lemma
-- Consider graph G, edge (u , v) in G, integer k >= 1. Let Gu = G with u and its incident edges deleted (similarly, Gv ). Then G
has a vertex cover of size k <=> Gu or Gv (or both) has a vertex cover of size (k - 1)
-- Proof:
<== Suppose Gu (say) has a vertex cover S of size k - 1. Write E = Eu (edges inside Gu) U Fu (edges incident to u). Since S has an endpoint of each edge of Eu, S U {u} is a vertex cover (of size k) of G.
==> Let S = a vertex cover of G of size k. Since (u , v) an edge of G, at least one of u , v (say u) is in S. Since no edges of Eu incident on u, S - {u} must be a vertex cover (of size k - 1) of Gu.
3. A Search Algorithm [Given undirected graph G = (V , E), integer k]
-- Pick an arbitrary edge (u , v) in E.
-- Recursively search for a vertex cover S of size (k - 1) in Gu.(G with u + its incident edges deleted). If found, return S U {u}.
-- Recursively search for a vertex cover S of size (k - 1) in Gv. If found, return S U {v}.
-- FAIL. [G has no vertex cover with size k]
4. Analysis of Search Algorithm
-- Correctness: Straightforward induction, using the substructure lemma to justify the inductive step.
-- Running time: Total number of recursive calls is O(2^k ) [branching factor <= 2, recursion depth <= k] (formally, proof by induction on k)
-- Also, O(m) work per recursive call (not counting work done by recursive subcalls)
-- Running time = O(m2^k) ==> Polynomial-time as long as k = O(log n) ==> better way than O(n^k)
5. The Traveling Salesman Problem
-- Input: A complete undirected graph with nonnegative edge costs.
-- Output: A minimum-cost tour (i.e., a cycle that visits every vertex exactly once).
-- Brute-force search: Takes about n! time
6. Hints from Bellman-Ford algorithm:
-- Proposed subproblems: For every edge budget i in {0, 1, . . . , n}, destination j in {1, 2, . . . . n}, let Lij = length of a shortest path from 1 to j that uses at most i edges. ==> can use less than i edges, solving all subproblems doesn't solve original problem.
-- Proposed subproblems: For every edge budget i in {0, 1, . . . , n}, destination j in {1, 2, . . . . n}, let Lij = length of a shortest path from 1 to j that uses exactly i edges. ==> can visit repeated vertex, solving all subproblems doesn't solve original problem.
-- Proposed subproblems: For every edge budget i in {0, 1, . . . , n}, destination j in {1, 2, . . . . n}, let Lij = length of a shortest path from 1 to j that uses exactly i edges and visit no repeated vertices. Hope : Lij = min(k<>1,j){ Li-1,k + ckj}
-- Problem: What if j already appears on the shortest 1 --> k path with (i - 1) edges and no repeated vertices? ==> Concatenating 1-->k and k-->j yields a second visit to j (not allowed)
-- Upshot: To enforce constraint that each vertex visited exactly once, need to remember the identities of vertices visited in subproblem. [But not the order in which they're visited]
7. The Subproblems
-- For every destination j in {1, 2, ... , n}, every S subset of {1, 2, ... , n} that contains 1 and j , let L(S,j) = minimum length of a path from 1 to j that visits precisely the vertices of S [exactly once each]
-- Let P be a shortest path from 1 to j that visits the vertices S (assume |S| >= 2) [exactly once each]. If last hop of P is (k , j ), then P' is a shortest path from 1 to k that visits every vertex of S - {j} exactly once.
-- Corresponding recurrence: L(S,j) = min(k in S,k<>j){L(S-{j} , k) + ckj} ["size" of subproblem = |S|]
8. A Dynamic Programming Algorithm
-- Let A = 2-D array, indexed by subsets S subset of {1, 2, ... , n} that contain 1 and destinations j in {1, 2, ... , n}
-- Base case: A[S , 1] = 0 if S = {1} ; +Infinity otherwise [no way to avoid visiting vertex 1 twice]
-- For m = 2, 3, ... , n [m = subproblem size]
For each set S in {1, 2, ... , n} of size m that contains 1
For each j in S, j <> 1
A[S , j ] = min(k in S, k<>j){A[S - {j} , k] + ckj} [same as recurrence]
-- Return min(j=2,...,n) { A[{1, 2, ... , n} , j ] + cj1 } [ min cost from 1 to j visiting everybody once + cost of final hop of tour]
-- Running time: O( n 2^n ) O(n) = O(n^2 2^n)
-- O(n 2^n) : choices of j * choices of S = # of subproblems
-- O(n) : work per subproblem
相关推荐
8 Approximation Algorithms for Geometric Problems Marshall Bern and David Eppstein 8.1 Introduction 8.1.1 Overview of topics 8.1.2 Special nature of geometric problems 8.2 Traveling salesman problem ...
algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is ...
**JEDEC JEP185:2021 Copy-Exact Process For Manufacturing** JEDEC(Joint Electron Device Engineering Council)是一个全球领先的微电子行业标准组织,致力于制定半导体存储器和其他相关技术的标准。JEP185是...
《JEDEC JEP185:2021 Copy-Exact Process For Manufacturing》是JEDEC固态技术协会发布的一份标准文档,旨在规范半导体制造过程中的复制精确工艺。这份22页的完整英文版资料详细阐述了如何在制造过程中实现一致性,...
VPRTW英文文档
【Fast and Memory-Efficient Exact Attention with IO-Awareness】,即Flash Attention,是一种针对Transformer模型的优化技术,尤其在处理长序列时能显著提升计算效率和内存利用率。Transformer架构中的自注意力...
EXACT STRING MATCHING ALGORITHMS 集大成之作
minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature ...
Exact Exponential Algorithms Authors: Fomin, Fedor V., Kratsch, Dieter
带坍塌项的非线性波动方程解爆破和整体解存在的精确条件,蒋毅,张永乐,本文考虑带坍塌项的非线性波动方程。在经典非线性椭圆方程中运用Gagliardo-Nirenberg 不等式, 我们建立了新的不变集。从而得到方程解爆�
Boussinesq-Burgers浅水方程的精确解,王雷,,Boussinesq-Burgers (B-B) 方程用来描述浅水中的长波传播并对港口和海岸设计有潜在的应用。本文利用变量变换和符号计算,通过朗斯基技术的�
本文深入探讨了各向同性湍流中Karman-Howarth方程的精确解问题,是由冉政撰写的首发论文。文章利用冯·卡门(von Karman)的自保持假设,得到了三维和二维各向同性湍流Karman-Howarth方程的四种不同的精确解。...
《古代精确科学》是奥托·诺伊格鲍尔(O. Neugebauer)所著的一部关于古代精确数学的描述性著作,作者通过对古代数学的深入研究,为读者提供了丰富的数学史知识以及相关背景信息。该书不仅探讨了数学本身的发展,...
这篇论文主要探讨了时间空间分数阶广义吉布斯-朗道方程(Ginzburg-Landau equation)在浅水尾流中的守恒定律和精确解。浅水尾流是指水流遇到障碍物(如岛屿或岬角)时分裂形成的类似尾巴的流动,其横向尺度远大于...