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

我们还是以顶点覆盖问题为例

介绍线性规划松弛方法

回顾加权顶点覆盖问题

给定一个图G

每个顶点上有一个非负权重

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

比如下图中蓝色的点构成一个顶点覆盖

目标值为55

对于加权顶点覆盖问题

我们可以用整数规划来刻画它

令xi为0-1变量

等于1表示它在顶点覆盖中

等于0表示它不在顶点覆盖中

顶点覆盖问题就对应于变量的取值问题

目标函数为最小化顶点覆盖中

顶点的权重之和

即minimizeΣw_ix_i

对于E中的边(i,j)

顶点覆盖中至少包含i和j中的一个

即x_i+x_j≥1

我们完整的写出加权顶点覆盖问题的

整数规划模型如下

我们称这个模型为ILP

一个直接的结果是

若x^*是ILP的最优解

那么令S=这个解中所有取值为1的变量

对应的顶点集合

S是一个最小的加权顶点覆盖

我们的算法需要用到一些线性规划的知识

线性规划是运筹学中一个最基本的问题

在理论和应用上都有非常重要的作用

线性规划问题是给定一些线性不等式约束

最大或最小化一个线性目标函数

输入是决定线性不等式约束

和线性目标函数的参数c_j,b_i,a_ij

一般假定它们都是整数

目标是求实值的非负变量x_j的值

在1947年Dantzig提出了著名的单纯形算法

它可以解决大多的实际问题

但却不是一个多项式时间算法

直到1979年

Khachian提出了第一个求解线性规划的

多项式时间算法

椭球法

但它的实际效果却不好

1984年 Karmarkar提出了内点法

它不仅是一个多项式时间算法

而且实际的效率很高

对于加权顶点覆盖问题的整数规划模型ILP

它的困难之处在于变量是0-1的

我们考虑把这个约束松弛掉

得到一个线性规划松弛问题LP

其变量是非负的

一个简单的发现是

LP的最优值≤ILP的最优值

这是因为LP有更少的约束

即ILP的任何可行解都是LP的可行解

还要注意的是LP不等同于ILP

对于右图中的例子

求解LP问题

可能得到每个顶点对应的变量值都是1/2

不是我们需要的整数解

是否可以利用求解LP问题

来得到一个好的顶点覆盖呢

我们将求解LP问题

然后通过舍入的方法

得到ILP问题的可行解

LP问题求得的最优解x^*

令S={i∈V:x^*_i≥½}

那么可以证明所得到的S

是一个顶点覆盖

并且对应的目标值

最多为最优值的两倍

先来证明S是一个顶点覆盖

考虑任意一条边(i,j)∈E

因为x^*_i+x^*_j≥1

所以x^*_i和x^*_j至少有一个≥½

因此顶点i,j之中至少有一个属于S

即S是一个顶点覆盖

再证解的质量

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

首先最优解也是LP问题的一个可行解

所以最优值

即S^*中顶点的权重和≥LP问题的最优值

≥S中顶点对应的权重与x^*_i乘积之和

而S中顶点i

满足x^*_i≥½

那么它≥½S中顶点的权重之和

命题得证

综合以上讨论

我们有LP松弛算法

对于加权顶点覆盖问题是2近似的

Dinur和Safra在2001年证明了

如果P≠NP

那么对于顶点覆盖问题

不存在近似比好于1.3607的近似算法

一个开放问题是

是否可以缩小近似和不可近似

结果之间的距离

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

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

LP Rounding: Vertex Cover在线视频