近似算法设计与分析技术

需积分: 10 51 浏览量更新于2024-07-18 收藏 3.27MB PDF 举报

"Design and Analysis of Approximation Algorithms" 本书的主要目的是为研究生提供一本教科书，用于学习理论计算机科学，特别是近似算法的设计和分析。同时，该书也可以作为研究人员在近似算法领域的参考书籍。近似算法是理论计算机科学中一个重要的研究方向。近似算法的设计和分析是研究人员和学生需要掌握的重要技能。本书采取了一种结构化的、技术导向的方法，按照算法的设计技术将近似算法分成不同的章节。这样可以帮助读者更好地理解近似算法的设计和分析技术，并且有助于教师以一种更统一的方式呈现近似算法的思想和技术。近似算法的设计和分析需要结合实际问题和应用场景。例如，几何优化问题、代数优化问题、组合优化问题等都是近似算法的重要应用领域。这些问题的解决需要使用不同的近似算法，例如贪心算法、动态规划算法、线性规划算法等。因此，本书将近似算法分成不同的章节，每章节都集中讨论特定的近似算法设计技术和分析方法。本书的内容还包括近似算法在优化领域的应用。优化问题是数学和计算机科学中一个核心的问题，它涉及到许多领域，例如操作研究、管理科学、经济学、生物信息学等。近似算法在优化领域的应用可以帮助研究人员和学生更好地解决实际问题。本书的主要目的是提供一个结构化的、技术导向的近似算法设计和分析方法，帮助研究人员和学生更好地理解近似算法的设计和分析技术，并且在优化领域中应用近似算法解决实际问题。资源标签：Approximation Algorithms 资源描述：本书是理论计算机科学研究生学习近似算法设计和分析的教科书，也可以作为研究人员在近似算法领域的参考书籍。

1.1 Open Sesame

k =1,...,n.Infact,ifs

>S, then we must have x

=0, and so we need not

consider the kth item at all. This assumption implies that opt ≥ max

1≤k≤n

There are many different approaches to attacking the KNAPSACK problem. First,

let us use the dynamic programming technique to ﬁnd the exact solutions for KNAP-

SACK.

To simplify the description of the algorithm, we ﬁrst deﬁne some notations. For

any subset I ⊆{1,...,n},letS

denote the sum



k∈I

. For each pair (i, j),

with 1 ≤ i ≤ n, 0 ≤ j ≤



i=1

, if there exists a set I ⊆{1, 2,...,n} such that



k∈I

= j and S

≤ S,thenleta(i, j) denote such a set I with the minimum

. If such an index subset I does not exist, then we say that a(i, j) is undeﬁned,

and write a(i, j)=nil.

Using the above notation, it is clear that opt =max{j | a(n, j) = nil}.There-

fore, it sufﬁces to compute all values of a(i, j). The following algorithm is based on

this idea.

Algorithm 1.A (Exact Algorithm for KNAPSACK)

Input: Positive integers S, s

,...,s

,...,c

(1) Let c

sum

←



i=1

(2) For j ← 0 to c

sum

if j =0then a(1,j) ←∅

else if j = c

then a(1,j) ←{1} else a(1,j) ← nil.

(3) For i ← 2 to n do

for j ← 0 to c

sum

if [a(i − 1,j−c

) = nil] and [S

a(i−1,j−c

)

≤ S − s

]

and [a(i − 1,j) = nil ⇒ S

a(i−1,j)

a(i−1,j−c

)

+ s

]

then a(i, j) ← a(i − 1,j− c

) ∪{i}

else a(i, j) ← a(i − 1,j).

(4) Output c

∗

← max{j | a(n, j) = nil}.

It is not hard to verify that this algorithm always ﬁnds the optimal solutions to

KNAPSACK (see Exercise 1.1).

Next, we consider the time complexity of Algorithm 1.A. Since Ali Baba had to

load the treasures and leave the cave before the Forty Thieves came back, he needed

an efﬁcient algorithm. It is easy to see that, for any I ⊆{1,...,n}, it takes time

O(n log S) to compute S

Thus, Algorithm 1.A runs in time O(n

M log(MS))

where M =max{c

| 1 ≤ k ≤ n} (note that c

sum

= O(nM )). We note that

We use the standard pseudocodesto describe an algorithm; see, e.g., Cormen et al. [2001].

In the rest of the book, we write log k to denote log

Introduction

the input size of the problem is n log M +logS (assuming that the input integers

are written in the binary form). Therefore, Algorithm 1.A is not a polynomial-time

algorithm. It is actually a pseudo-polynomial-timealgorithm, in the sense that it runs

in time polynomial in the maximum input value but not necessarily polynomial in

the input size. Since the input value could be very large, a pseudo polynomial-time

algorithm is usually not considered as an efﬁcient algorithm. To be sure, if Ali Baba

tried to run this algorithm, then the Forty Thieves would deﬁnitely have come back

before he got the solution—even if he could calculate as fast as a modern digital

computer.

As a compromise, Ali Baba might ﬁnd a fast approximation algorithm more use-

ful. For instance, the following is such an approximation algorithm, which uses a

simple greedy strategy that selects the heaviest item (i.e., the item with the greatest

density c

)ﬁrst.

Algorithm 1.B (Greedy Algorithm for KNAPSACK)

Input: Positive integers S, s

,...,s

,...,c

(1) Sort all items in the nonincreasing order of c

. Without loss of generality,

assume that c

≥ c

≥···≥c

(2) If



i=1

≤ S then output c

←



i=1

else k ← max







i=1

≤ S<

j+1



i=1



;

output c

← max



k+1



i=1



It is clear that this greedy algorithm runs in time O(n log(nM S)) and hence is

very efﬁcient. The following theorem shows that it produces an approximate solu-

tion not very far from the optimum.

Theorem 1.1 Let opt be the optimal solution of the problem KNAPSACK and c

the approximate solution obtained by Algorithm 1.B.Thenopt ≤ 2c

(and we say

that the performance ratio of Algorithm 1.B is bounded by the constant 2).

Proof. For convenience, write c

∗

for opt.If



i=1

≤ S,thenc

= c

∗

.Thus,we

may assume



i=1

>S.Letk be the integer found by Algorithm 1.B in step (2).

We claim that



i=1

≤ c

∗

k+1



i=1

. (1.1)

The ﬁrst half of the above inequality holds trivially. For the second half, we note

that, in step (1), we sorted the items according to their density, c

. Therefore, if

we are allowed to cut each item into smaller pieces, then the most efﬁcient way of

using the knapsack is to load the ﬁrst k items, plus a portion of the (k +1)st item

that ﬁlls the knapsack, because replacing any portion of these items by other items

1.1 Open Sesame

decreases the total density of the knapsack. This shows that the maximum total value

∗

we can get is less than



k+1

i=1

We can also view the above argument in terms of linear programming. That is,

if we replace the constraints x

∈{0, 1} by 0 ≤ x

≤ 1, then we obtain a linear

program which has the maximum objective function value ˆc ≥ c

∗

. It is easy to check

that the following assignment is an optimal solution to this linear program

⎧

⎪

⎨

⎪

⎩

1, for j =1, 2,...,k,



S −



i=1



k+1

, for j = k +1,

0, for j = k +2,...,n.

Therefore,

∗

≤ ˆc =



i=1

k+1



S −



i=1





i=1

k+1



i=1

Finally, it is obvious that, from (1.1), we have

=max



k+1



i=1



≥

k+1



i=1

∗

. 

The above two algorithms demonstrate an interesting tradeoff between the run-

ning time and the accuracy of an algorithm: If we sacriﬁce a little in the accuracy

of the solution, we may get a much more efﬁcient algorithm. Indeed, we can further

explore this idea of tradeoff and show a spectrum of approximation algorithms with

different running time and accuracy.

First, we show how to generalize the above greedy algorithm to get better ap-

proximate solutions—with worse, but still polynomial, running time. The idea is

as follows: We divide all items into two groups: those with values c

≤ a and

those with c

>a,wherea is a ﬁxed parameter. Note that in any feasible solution

I ⊆{1, 2,...,n}, there can be at most opt/a ≤ 2c

/a items that have values

greater than a. So we can perform an exhaustive search over all index subsets

I ⊆{1, 2,...,n} of size at most 2c

/a from the second group as follows: For

each subset I, use the greedy strategy on the ﬁrst group to get a solution of the to-

tal volume no greater than S − S

, and combine it with I to get an approximate

solution. From Theorem 1.1, we know that our error is bounded by the value of a

single item of the ﬁrst group, which is at most a. In addition, we note that there are

at most n

index subsets of the second group to be searched through, and so the

running time is still a polynomial function in the input size.

In the following, we write |A| to denote the size of a ﬁnite set A.

Algorithm 1.C (Generalized Greedy Algorithm for KNAPSACK)

Input: Positive integers S, s

,...,s

,...,c

, and a constant 0 <ε<1.

See Chapter 7 for a more complete treatment of linear programming.

剩余452页未读，继续阅读

ignite678@126.com

粉丝: 2
资源: 42

近似算法设计与分析技术

《Design and Analysis of Approximation Algorithms》

Introduction to the Design and Analysis of Algorithms 2nd 课后解答

integral_approximation = 0 for i in range(n): x_i = a + i * h integral_approximation += func(x_i) * h integral_approximation是什么

cannot import name 'hamiltonian_path' from 'networkx.algorithms.approximation' (C:\Users\86182\anaconda3\lib\site-packages\networkx\algorithms\approximation\__init__.py)

module 'networkx.algorithms.approximation' has no attribute 'hamiltonian_path'

写出用泰勒公式求ln2的近似值的代码，要求用三种不同的麦克劳林展开式

Python π 可以用以下公式来计算: π=4×(1-1/3+1/5-1/7+1/9-1/11+⋯) 编写一个程序显示 4×(1-1/3+1/5-1/7+1/9-1/11) 和 4×(1-1/3+1/5-1/7+1/9-1/11+1/13-1/15).的结果

写一个函数riemann_approximation，它接受4个参数作为输入，一个函数f，区间端点a < b 和一个正整数 n ，并使用n + 1 点返回[ a , b ] 上的Riemann和近似值到[ a , b ]。

geometric_approximation的原理

最新资源

cannot import name 'hamiltonian_path' from 'networkx.algorithms.approximation' (C:\Users\86182\anaconda3\lib\site-packages\networkx\algorithms\approximation\init.py)