The Pricing Method: Vertex Cover慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

下面我们以顶点覆盖问题为例

介绍几种常用的近似算法设计的技术

先来看一下定价方法

我们考虑加权顶点覆盖问题

给定一个图G

每个顶点上有个非负权重

求一个总权重最小的顶点覆盖

比如下图中

最小顶盖覆盖为三个蓝色的点

目标值为8

下面介绍定价方法

每条边都需要被某个顶点i所覆盖

那么边e需要对顶点i

支付一个非负的费用p_e

制定费用函数需要考虑公平的因素

我们要求每个顶点i所关联的

边上的总费用不超过它的权重w_i

对于任意的顶点覆盖S

和任何的公平的费用函数

我们有Σp_e≤w(S)

即所有边上的总费用

不超过S中顶点的总权重

首先 Σp_e≤对S中的点i

所有与它关联的边上定价之和

再对i进行求和

这是因为S是一个顶点覆盖

每条边e至少在S中关联一个顶点

因为定价是公平的

所以它≤S中所有点的权重和

也就是w(S)

我们先给出定价方法的伪代码

它同时确定定价函数

和求出一个顶点覆盖

先令S为空集

对于E中的每条边e

令它的定价为0

如果存在一条边(i,j)

其两个端点都不是紧的

即其关联边上的定价之和小于它的权重

那么就尽可能的增加边e的定价

使得i或j是紧的

令S为最后紧的端点的集合

最后返回S

我们来看一个例子

初始的时候

S为空集

令每条边的定价为0

边(a,b)的两个端点都不是紧的

选择这条边

两个端点的权重分别为3和4

那么这条边的定价为3

边(a,d)的两个端点都不是紧的

选择这条边

这条边可以定价为1

这时顶点a是紧的

边(c,d)的两个端点都不是紧的

选择这条边

这条边可以定价为2

这时顶点d是紧的

注意到这时候任何一条边的两个端点

至少有一个紧的

算法结束

S={a,b,c}

目标值为10

我们将证明定价方法是2近似的

算法每一步

都至少把一个紧的顶点放入S中

所以算法有限步终止

令S为算法终止时返回的所有紧的顶点

那么S是一个顶点覆盖

这是因为

如果有一条边(i,j)没有被覆盖

那么它的两个顶点i和j一定都不是紧的

算法也就不会终止

令S^*是最优的顶点覆盖

我们证明w(S)≤2w(S^*)

w(S)等于S中所有顶点的权重和

因为S中的顶点都是紧的

它等于S中所有顶点的

与其关联的边上定价之和

把集合S扩大为集合V

我们得到它小于等于

V中所有顶点的与其关联的边上定价之和

注意到在这个求和中

每个pe出现了2次

因此等于2倍的所有边上定价之和

再根据之前证明的引理

我们得到它≤2w(S^*)

算法设计与分析课程列表：

1 Introduction of Algorithm

-1.1 Introduction

--Introduction

-1.2 A First Problem: Stable Matching

--A First Problem: Stable Matching

-1.3 Gale-Shapley Algorithm

--Gale-Shapley Algorithm

-1.4 Understanding Gale-Shapley Algorithm

--Understanding Gale-Shapley Algorithm

-Homework1

-Lecture note 1

--Lecture note 1 Introduction of Algorithm

2 Basics of Algorithm Analysis

-2.1 Computational Tractability

--Computational Tractability

-2.2 Asymptotic Order of Growth

--Asymptotic Order of Growth

-2.3 A Survey of Common Running Times

--A Survey of Common Running Times

-Homework2

-Lecture note 2

--Lecture note 2 Basics of Algorithm Analysis

3 Graph

-3.1 Basic Definitions and Applications

--Basic Definitions and Applications

-3.2 Graph Traversal

--Graph Traversal

-3.3 Testing Bipartiteness

--Testing Bipartiteness

-3.4 Connectivity in Directed Graphs

--Connectivity in Directed Graphs

-3.5 DAG and Topological Ordering

--DAG and Topological Ordering

-Homework3

-Lecture note 3

--Lecture note 3 Graph

4 Greedy Algorithms

-4.1 Coin Changing

--Coin Changing

-4.2 Interval Scheduling

--Interval Scheduling

-4.3 Interval Partitioning

--Interval Partitioning

-4.4 Scheduling to Minimize Lateness

--Scheduling to Minimize Lateness

-4.5 Optimal Caching

--Optimal Caching

-4.6 Shortest Paths in a Graph

--Shortest Paths in a Graph

-4.7 Minimum Spanning Tree

--Minimum Spanning Tree

-4.8 Correctness of Algorithms

--Correctness of Algorithms

-4.9 Clustering

--Clustering

-Homework4

-Lecture note 4

--Lecture note 4 Greedy Algorithms

5 Divide and Conquer

-5.1 Mergesort

--Mergesort

-5.2 Counting Inversions

--Counting Inversions

-5.3 Closest Pair of Points

--Closest Pair of Points

-5.4 Integer Multiplication

--Integer Multiplication

-5.5 Matrix Multiplication

--Video

-5.6 Convolution and FFT

--Convolution and FFT

-5.7 FFT

--FFT

-5.8 Inverse DFT

--Inverse DFT

-Homework5

-Lecture note 5

--Lecture note 5 Divide and Conquer

6 Dynamic Programming

-6.1 Weighted Interval Scheduling

--Weighted Interval Scheduling

-6.2 Segmented Least Squares

--Segmented Least Squares

-6.3 Knapsack Problem

--Knapsack Problem

-6.4 RNA Secondary Structure

--RNA Secondary Structure

-6.5 Sequence Alignment

--Sequence Alignment

-6.6 Shortest Paths

--Shortest Paths

-Homework6

-Lecture note 6

--Lecture note 6 Dynamic Programming

7 Network Flow

-7.1 Flows and Cuts

--Flows and Cuts

-7.2 Minimum Cut and Maximum Flow

--Minimum Cut and Maximum Flow

-7.3 Ford-Fulkerson Algorithm

--Ford-Fulkerson Algorithm

-7.4 Choosing Good Augmenting Paths

--Choosing Good Augmenting Paths

-7.5 Bipartite Matching

--Bipartite Matching

-Homework7

-Lecture note 7

--Lecture note 7 Network Flow

8 NP and Computational Intractability

-8.1 Polynomial-Time Reductions

--Polynomial-Time Reductions

-8.2 Basic Reduction Strategies I

--Basic Reduction Strategies I

-8.3 Basic Reduction Strategies II

--Basic Reduction Strategies II

-8.4 Definition of NP

--Definition of NP

-8.5 Problems in NP

--Problems in NP

-8.6 NP-Completeness

--NP-Completeness

-8.7 Sequencing Problems

--Sequencing Problems

-8.8 Numerical Problems

--Numerical Problems

-8.9 co-NP and the Asymmetry of NP

--co-NP and the Asymmetry of NP

-Homework8

-Lecture note 8

--Lecture note 8 NP and Computational Intractability

9 Approximation Algorithms

-9.1 Load Balancing

--Load Balancing

-9.2 Center Selection

--Center Selection

-9.3 The Pricing Method: Vertex Cover

--The Pricing Method: Vertex Cover

-9.4 LP Rounding: Vertex Cover

--LP Rounding: Vertex Cover

-9.5 Knapsack Problem

--Knapsack Problem

-Homework9

-Lecture note 9

--Lecture note 9 Approximation Algorithms

10 Local Search

-10.1 Landscape of an Optimization Problem

--Landscape of an Optimization Problem

-10.2 Maximum Cut

--Maximum Cut

-10.3 Nash Equilibria

--Nash Equilibria

-10.4 Price of Stability

--Price of Stability

-Homework10

-Lecture note 10

--Lecture note 10 Local Search

11 Randomized Algorithms

-11.1 Contention Resolution

--Contention Resolution

-11.2 Linearity of Expectation

--Linearity of Expectation

-11.3 MAX 3-SAT

--MAX 3-SAT

-11.4 Chernoff Bounds

--Chernoff Bounds

-Homework11

-Lecture note 11

--Lecture note 11 Randomized Algorithms

Exam

-Exam

The Pricing Method: Vertex Cover在线视频