高维空间近似最小球覆盖问题的研究

摘要

本文主要讨论高维空间球集最小球覆盖问题和二维空间圆集最小圆覆盖问题。
　　 高维空间最小球覆盖问题是指对于给定的高维空间球集S，求解覆盖S中所有球的最小球。
　　 二维空间最小圆覆盖问题是高维空间最小球覆盖问题的特例（维数d=2）。
　　 点集和圆集的覆盖问题目前已经有很多求解算法。由于这些算法对内存的过度需求，导致我们无法在合理的时间内求解大数据量问题。Badoiu提出了核心集的概念，降低了求解该问题的复杂性。本文通过引入核心集的思想，改进了球集和圆集覆盖问题的各种算法。
　　 提出了球集直径的概念，给出了求解球集直径的近似算法，并证明了该算法至少可以得到1/3倍球集直径近似值。
　　 给出了求解高维空间球集最小球覆盖问题的1+ε近似算法。其中核心集的大小为0（1/ε），算法的时间复杂度为O（nd/ε+(d2/ε3/2)(1/ε+d)log(1/ε)）。
　　 通过引入核心集的思想，改进了二维空间圆集最小圆覆盖问题的各种求解算法，给出了求解该问题的1+ε近似算法。
　　 第2.4节和第3.4节对各种算法进行了实验对比。

目录

文摘

英文文摘

TABLE OF CONTENTS

第1章 绪论

1.1 应用背景及问题描述

1.1.1 应用背景

1.1.2 问题描述

1.2 研究现状

1.3 研究方法

1.4 论文的组织结构

第2章 高维空间球集覆盖问题

2.1 问题简介

2.2 球集直径及初始核心集

2.3 1+ε近似算法

2.4 SOCP介绍及实验结果

2.4.1 SOCP介绍

2.4.2 实验结果

第3章 二维空间圆覆盖问题

3.1 圆覆盖问题简介

3.2 圆覆盖问题求解算法

3.2.1 二阶锥规划

3.2.2 次梯度方法

3.2.3 二次规划

3.2.4 随机增量算法

3.3 利用核心集求解圆覆盖问题

3.4 实验结果

3.4.1 二阶锥规划与算法3.4的实验结果

3.4.2 次梯度方法与算法3.4的实验结果

3.4.3 二次规划与算法3.4的实验结果

3.4.4 二阶锥规划，算法3.1与算法3.2实验结果比较

3.4.5 随机增量算法与算法3.4的实验结果

3.5 结论

第4章 总结与展望

4.1 总结

4.2 展望

参考文献

致谢

攻读硕士期间发表的学术论文目录

学位论文评阅及答辩情况表