图的随机p-中心和中位问题的理论和算法研究

The p-center and p-median problems in graphs are important topics in operation research and algrothmic graph theory, which are closely related to domination and vertex cover problems in graphs. They have many applications in communication，complexity network, transportation and environmental science. In the classical location model, it is required to locate facilities on a network so as to minimimize the cost incurred by customers. Traditionally, location analysis has been concerned with frameworks where all the data describing an instance of a problem are known precisely. However, in real world situations, most of the times it is impossible to make accurate estimations of those data that, very often, are affected by uncertainty. The probabilistic minmax problem and probabilistic median problem are motivated and studied. In this project we will study stochastic p-center and p-median problems, reliable facility location under disruption, connected p-center problem by using graph theory, combinatorial optimization and probabilistic methods. We will present complexity analysis and approximation algorithms for the problems on graphs and hypegraphs. We will give polynomial time algorithms for some special graphs such as graphs with bounded treewidth, outplanar graphs, AT-free graphs and hypertrees. This project involves in algorithmic graph theory, combinatorial optimization and random optimization. The research will have a positive effect on graph theory, network optimization,hypegraph theory and theoretical computer science.

图的中心和中位问题是运筹学和算法图论的重要研究内容，与图的控制集和覆盖集密切相关，在通讯、复杂网络、运输和环境科学中有着广泛应用。经典的选址问题是在网络上放置设施, 以使得设施的布局能为顾客提供更加方便的服务。经典的选址模型中所有数据都是确定的。由于现实世界的复杂性，需求点位置、需求数量等部分或全部输入参数经常是不确定的, 由此产生了随机选址问题。本项目将从图论角度利用图的组合结构，并结合优化方法和概率方法对图上的随机p-中心和p-中位问题，设施可能失效的p-中心以及具有连通约束的p-中心等进行研究。讨论这些问题在一般图和超图上的计算复杂性和近似算法，并通过分析树宽有界图、外平面图、AT-free图和超树等图类的结构性质，设计它们在这些图类上的多项式算法。本项目研究的内容涉及算法图论、组合最优化、超图理论和随机优化。这些问题的解决对推动图论、网络优化与理论计算机科学的交叉研究具有重要意义。

网络选址问题是运筹学与管理科学中的重要问题，是图论与组合优化领域得重要研究课题，其在交通、通讯和城市其他服务设施的建设中具有重要的应用。针对实际问题，我们考虑了树状结构网络中上两条路的选址问题, 也就是选择两条路使得树上所有点到这两条路的加权距离和达到最小。我们分析了问题的最优解的性质，并给出了求解此问题的多项式时间算法。研究了连通的设施选址问题,对树状结构网络的连通设施选址问题，给出了多项式时间算法。此外，对等价二元树上的连通设施选址问题，给出了时间为O(np)的多项式算法。研究了块图的连通设施选址问题,我们证明了对具有单位边长的块图，极小化网络中的所有点到p-顶点子集的加权距离之和是线性时间可解的；其次讨论了极小化这个p-顶点子集之外的每个顶点到这个p-顶点子集的最大距离，同时极小化所有点到这个p-顶点子集的距离之和。证明了其Pareto-optimal解集的基数不超过n, 而且能够在多项式时间里获得。这些研究成果推进了文献中已有的相关工作,研究成果以学术论文地形式呈现。在国际重要期刊《Journal of Combinatorial Optimization》、《Theoretical Computer Science》、《Journal of Graph Theory》、《The Electronic Journal of Combinatorics》、《European Journal of Combinatorics》、《Linear Algebra and its Applications》、《Discrete Mathematics》等发表学术论文35篇。其中在组合图论的顶级期刊《Journal of Graph Theory》发表学术论文2篇。