近似算法：NP-hard优化问题的多项式时间设计概览

需积分: 10 184 浏览量更新于2024-07-27 收藏 843KB PDF 举报

本资源是一本关于近似算法的教材，由Vijay Vazirani撰写，收录于佐治亚理工学院的计算机科学学院。这本书旨在介绍如何设计在多项式时间内求解NP完全优化问题的近似算法，对于计算机科学特别是理论计算机科学领域具有重要意义。章节内容涵盖了多个核心主题，包括： 1. **组合算法**：这部分探讨了集合覆盖问题及其应用，例如寻找最短超级字符串，这是通过组合优化技术解决的经典问题，涉及最小化覆盖元素数量以达到给定目标。 2. **度量空间中的Steiner树和TSP（旅行商问题）**：这些是图论中的经典问题，Steiner树涉及在图中添加最少边以连接特定的一组顶点，而TSP则涉及寻找访问所有顶点一次且总距离最小的路径。近似算法为这类问题提供了高效但不一定是最优的解决方案。 3. **多边形切割和k-cut问题**：涉及在多边形内部或边界上划分，以减少区域间的连接成本，常用于设施定位和网络设计。 4. **反馈 Vertex Set**：研究的是如何在一个图中删除最少的顶点，使得剩下的图成为森林，这是一种重要的图论问题，也与网络设计和故障恢复策略有关。 5. **最短超级字符串和背包问题**：前者涉及找到一个字符串序列，使其包含所有其他字符串，而后者则是优化选择物品以满足容量限制，同时最大化价值。 6. **最小Makespan调度**：在资源分配问题中，力求在给定时间窗口内完成任务，找到最小的总工作时间安排。 7. **线性规划（LP）基础算法**：这部分介绍了如何利用线性规划的原理设计近似算法，包括LP对偶性分析，以及 primal-dual方法在多连通图中的应用，如Multicut问题。 8. **稀疏割问题**：研究的是最小化图中割的权重，它在通信网络设计和数据传输效率中扮演关键角色。这本书通过一系列实际问题的探讨，展示了如何将复杂优化问题转化为可计算的近似解，为理解计算机科学中的优化难题提供了一种实用的理论框架。对于想要深入学习近似算法和求解复杂问题的学生和研究人员来说，这是一本不可或缺的参考书。

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 (

s

), 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 byatmosttwoofthe



'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 requirementisalso

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 eachstring

,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

hascostatmost2



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 number (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



(

)

,TSPcannot 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 w

e 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页未读，继续阅读

zhru00

粉丝: 0
资源: 2

近似算法：NP-hard优化问题的多项式时间设计概览

hw2_algorithm_

266.rar_Type-2_fuzzy approximation _interval_interval fuzzy _int

Skiena-The_Algorithm_Design_Manual.pdf

The design of approximation algorithm_D. P. Williamson

approximation algorithm

Experimenting an Approximation Algorithm

近似算法 approximation algorithm

相似性算法APPROXIMATION ALGORITHM

d-无爪图中最大权独立集问题的一种改进逼近算法_An Improved Approximation Algorithm for

Fast calculation of bistatic RCS for conducting objects using the adaptive cross approximation algorithm

最新资源