近似算法：Vazirani的经典著作

需积分: 10 151 浏览量更新于2024-07-22 3 收藏 874KB PDF 举报

"approximation algorithms — Vijay V. Vazirani" 这本由Vijay V. Vazirani编写的《approximation algorithms》是一本关于近似算法的经典著作，专注于探讨如何在不能找到最优解的情况下，寻找接近最优解的有效算法。近似算法在实际问题中尤为重要，因为许多计算问题是NP-hard的，这意味着找到精确解在多项式时间内是不可行的。 1. **组合优化算法**： - **集合覆盖**：这是一个基础的组合优化问题，目标是用最少数量的集合来覆盖所有给定的元素。书中可能讨论了如何通过贪心策略或拉格朗日松弛等方法设计近似算法，解决其在最短超字符串问题中的应用。 - **多路划分和k-划分**：这些问题涉及将图的顶点集分成尽可能小的子集，同时保持某些连接条件。多路划分关注的是分割成k条路径，而k-划分则是分割成k个不相交的子集。近似算法可能包括基于边权重的方法和局部搜索策略。 2. **度量Steiner树与旅行商问题(TSP)**： - **Steiner树**：在给定加权图中，找到连接所有指定顶点的最小权重树，其中非终端节点称为Steiner点。书里可能介绍了几种近似算法，如贪心算法、基于网络流的方法和动态规划策略。 - **TSP**：旅行商问题寻找访问每个城市一次并返回起点的最短路径。经典的近似算法有Christofides算法和2-approximation算法，书可能详细解释了这些方法的原理和实现。 3. **设施定位问题**：在这类问题中，目标是决定在哪里放置设施以满足客户需求，同时最小化成本。可能涵盖的近似算法包括贪婪算法、局部搜索和LP-relaxation技术。 4. **反馈顶点集**：反馈顶点集问题要求找出一个最小大小的顶点集，删除后使图变为无环。这个问题在图简化和网络可靠性分析中有应用。书可能介绍了基于割点和割边的近似算法。除了以上核心内容，这本书还可能涵盖其他近似算法主题，如网络设计、分配问题、图着色、匹配问题等。Vazirani教授的这本书以其深入浅出的讲解和丰富的实例，为读者提供了理解近似算法理论和实践的坚实基础。对于计算机科学特别是算法研究和实践者来说，这是一份宝贵的资源。

overlaps with

(there exists at least one such string, namely

itself ). In general, if

we set

+ 1 and denote by

the largest index of a string that overlaps with

.Eventually,

we will get

for some



For each pair of strings (

), let

0 be the length of the overlap b etween their leftmost

occurrences in

(this may b e dierent from their maximum overlap). Let





. Clearly,

set(



)



is a solution for

, of cost



The critical observation is that



does not overlap



.We will prove this claim for

=1;

the same argument applies to arbitrary

. Assume for a contradiction that



overlaps



. Then

the o ccurrence of

overlaps the occurrence of

. Because

, it follows that the

occurrence of

overlaps the o ccurrence of

. Ths contradicts the fact that

is the highest

indexed string that overlaps with

Because of this observation, eachsymbol of

is covered by at most two of the



's. Hence

OPT





j



OPT.

Lemma 2.8 immediately gives:

Theorem 2.9

Algorithm 2.7 is a



factor algorithm for the shortest superstring problem.

Exercise 2.10

A more elab orate argumentshows that in fact Algorithm 2.2 achieves an ap-

proximation factor of

, where

is the cardinality of the largest sp ecied subset of

. Prove

this approximation guarantee.

Exercise 2.11

Show that a similar greedy strategy achieves an approximation guarantee of

for set multi-cover, a generalization of set cover in whichanintegral coverage requirement is also

specied for each element, and sets can b e picked multiple numb er of times to satisfy all coverage

requirements. Assume that the cost of picking

alpha

copies of set





cost(

Exercise 2.12

By giving an appropriate tight example, show that the analysis of Algorithm

2.2 cannot b e improved even if all sp ecied sets have unit cost. Hint: Consider running the greedy

algorithm on a vertex cover instance.

Exercise 2.13

The

maximum coverage problem

is the following: Given a universe

elements, with non-negativeweights specied, a collection of subsets of

;:::;S

, and an integer

, pick

sets so as to maximize the weight of elements covered. Show that the obvious algorithm,

of greedily picking the best set in each iteration until

sets are picked, achieves an approximation

factor of

;

)

;

)

Exercise 2.14

Using set cover, obtain approximation algorithms for the following variants of

the shortest superstring problem (here

is the reverse of string

1. Find the shortest string

that contains for each string

,both

and

as subtrings.

2. Find the shortest string

that contains for each string

, either

as a subtring.

(Notice that this suces for the data compression application given earlier.)

The cost of this Euler tour is 2



OPT. Next obtain a Hamilton tour on the vertices of

traversing the Euler tour and \short-cutting" Steiner vertices and previously visited vertices of

Because of triangle inequality, the shortcuts do not not increase the cost of the tour. If we delete

one edge of this Hamilton tour, we obtain a path that spans

and has cost at most 2



OPT. This

path is also a spanning tree on

. Hence, the MST on

has cost at most 2



OPT.

Theorem 3.2 gives a straightforward factor 2 algorithm for the metric Steiner tree problem:

simply nd an MST on the set of required vertices. As in the case of set cover, the \correct" way

of viewing this algorithm is in the setting of LP-duality theory. This will provide the lower b ound

on which this algorithm is based, and will also help solve generalizations of this problem.

Example 3.3

Atight example is provided by a graph with

required vertices and one Steiner

vertex. Each edge b etween the Steiner vertex and a required vertex has cost 1, and all other edges

have cost (2

;



), where

>

0 is a small numb er (not all edges of cost (2

;



) are shown below). In

this graph, an MST on

has cost (2

;



)(

;

1), while OPT =







;

(



Exercise 3.4

Let

V; E

) be a graph with non-negative edge costs. The vertices of

are

partitioned into two sets,

senders

and

receivers

. The problem is to nd a minimum cost subgraph

that has a path connecting each receiver to a sender. Give a goo d approximation algorithm

for this NP-hard problem.

Approximation algorithms for TSP

The following is a well-studied problem in combinatorial optimization.

Problem 3.5 (Traveling salesman problem (TSP))

Given a complete graph with non-

negative edge costs, nd a minimum cost cycle visiting every vertex exactly once.

Not only is it

-hard to solve this problem exactly, but also approximately:

Theorem 3.6

For any polynomial time computable function



(

)

, TSP cannot beapproximated

within a factor of



(

)

,unless

Metric Steiner tree and TSP

Proof :

Assume for a contradiction that for any graph on

vertices, we can nd in polynomial

time a salesman tour whose cost is within a factor of



(

) from the optimum. We show that this

implies a polynomial time algorithm for deciding whether a given graph has a Hamiltonian cycle.

Let

be a graph on

vertices. We extend

to the complete graph on

vertices, assigning

unit cost to edges of

, and a cost of

n

(

) to edges not in

. Clearly, the optimal salesman tour

in the new graph has a cost of

if and only if

has a Hamiltonian cycle. Moreover, any tour that

contains a new edge costs more than

n

(

). So, an



(

) approximation algorithm nds a tour of

cost

whenever one exists.

Notice that in order to obtain such a strong non-approximability result, we had to assign edge

costs that violate triangle inequality.Ifwe restrict ourselves to graphs in which edge costs satisfy

triangle inequality, i.e., the

metric traveling salesman problem

, the problem remains

-complete,

but it is no longer hard to approximate.

We will rst present a simple factor 2 algorithm. The lower bound we will use for obtaining

this factor is the cost of an MST in

. Thisisalower bound b ecause deleting any edge from an

optimal solution to TSP we get a spanning tree of

Algorithm 3.7 (Metric TSP { factor 2)

1. Find an MST,

,of

2. Double every edge of the MST to obtain an Eulerian graph.

3. Find an Euler tour,

,onthisgraph.

4. Output the tour that visits vertices of

in order of their rst appearence in

. Let

be this

tour.

Notice that Step 4 is similar to the \short-cutting" step in Theorem 3.2.

Theorem 3.8

Algorithm 3.7 is a factor 2 algorithm for metric TSP.

Proof :

As noted ab ove, cost(

)



OPT. Since

contains each edge of

twice, cost(



cost(

). Because of triangle inequality, after the \short-cutting" step, cost(

)



cost(

). Com-

bining these inequalities we get that cost(

)





OPT.

Example 3.9

A tight example for this algorithm is given by the complete graph on

vertices

with edges of cost 1 and 2. We present the graph for

=6below. The thick edges have cost 1 and

the remaining edges havecost2. On

vertices, the graph will have2

;

2 edges of cost 2, and the

remaining edges of cost 1, with the cost 2 edges forming the union of a star and an

;

1 cycle.

The optimal TSP tour has cost

as shown b elow.

r r



Q









Q





;





Suppose that the MST found by the algorithm is the spanning star created by edges of cost 1.

Moreover, supp ose that the Euler tour constructed in Step 3 visits vertices in order shown below:

r r







B





Then the tour obtained after short-cutting contains

;

2 edges of cost 2, and has a total cost of

;

2. This is almost twice the cost of the optimal TSP tour.

Essentially, this algorithm rst nds a low cost Euler tour spanning the vertices of

, and then

short-cuts this tour to nd a travelling salesman tour. Is there a cheaper Euler tour than that

found by doubling an MST? Notice that we only need to be concerned ab out the vertices of o dd

degree in the MST; let

denote this set of vertices.

must b e even since the sum of degrees

of all vertices in the MST is even (it is 2

;

2). Now, if we add to the MST a minimum cost

perfect matching on

,every vertex will haveeven degree, and we get an Eulerian graph. With

this mo dication, the algorithm achieves an approximation guarantee of

Algorithm 3.10 (Metric TSP { factor

)

1. Find an MST of

,say

2. Compute a minimum cost perfect matching,

, on the set of odd vertices of

.Add

and obtain an Eulerian graph.

3. Find an Euler tour,

, of this graph.

4. Output the tour that visits vertices of

in order of their rst appearence in

. Let

be this

tour.

Interestingly, the pro of of this algorithm is based on a second lower b ound on OPT .

Lemma 3.11

Let



, such that

is even, and let

be a minimum cost perfect matching

. Then,

cost(

)



OPT

Proof :

Consider an optimal TSP tour of

,say



. Let



be the tour on

obtained by

short-cutting



. By triangle inequality,cost(



)



cost(



). Now,



is the union of two perfect

matchings on

, each consisting of alternate edges of



. So, the cheaper of these matchings has

cost



cost

(



)



OPT

. Hence the optimal matching also has cost



OPT

Theorem 3.12

Algorithm 3.10 achieves an approximation guaranteeof

for metric TSP.

Proof :

The proof follows by putting together the twolower b ounds on OPT.

Example 3.13

A tight example for this algorithm is given by the following graph on

vertices:

S



S



S

S



& %

1 1 1

1 1

111

:::

剩余118页未读，继续阅读

不是助手的Chris

粉丝: 1
资源: 4

近似算法：Vazirani的经典著作

Approximation Algorithms

近似算法英文版（Approximation Algorithms）

Approximation.Algorithms.for.NP-Hard.Problems

Approximation Algorithms.zip

Approximation Algorithms.pdf

Approximation Algorithms.rar

Approximation Algorithms and Semidefinite Programming

近似算法（Approximation algorithms）

Outer approximation algorithms for separable nonconvex

Introduction to Stochastic Approximation Algorithms.pdf

最新资源