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

项目名称： 图的随机p-中心和中位问题的理论和算法研究

项目编号： No.11471210

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 康丽英

作者单位： 上海大学

项目金额： 75万元

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

中文关键词： 算法设计；控制数；中心；超图；控制集

英文摘要： 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.

英文关键词： Algorithm design;Domination number;Center;Hypergraph;Dominating set