离散选址类问题是指从给定集合中选择部分设施为一组客户提供服务，使得总服务成本最小。设施选址问题，即Facility Location（Uncapacitated Facility Location）问题，简称UFL问题，以及k中间点问题，简称k-median问题，是离散选址类问题中两个最具代表性的问题。前者定义了设施费用以及设施与客户之间的连接费用，要求选择部分设施与客户连接，使得被选中设施的费用与总连接费用之和最小；后者类似前者，要求至多选择k个设施与客户连接，总连接费用最小。两问题在区域规划、管理科学、通信和计算机科学等领域有着广泛的应用背景，例如城市公共设施的选址与建造，现代企业物流中心的布局，电信基站选址和网络路由等问题。UFL和k-median问题起源于1620年资产阶级企业投资人的一次讨论，当时人们希望在几个已存在的原材料生产基地附近，选择一中心位置建立产品加工厂，既满足各原材料生产基地的产品输出需求，又使得它们到产品加工厂的运输成本最小。后来，人们正式提出了为若干离散点选择单中心点的Fermat-Weber问题，它也成为了UFL和k-median问题的早期雏形。1963年Cooper正式提出了UFL问题，次年，Hamiki正式提出k-median问题并证明两问题均属于NP-hard难解问题。随后，运筹学和计算机科学领域的算法工作者对两问题进行了深入研究，他们利用各种方法分析问题，试图找到更加有效的解决方案得到问题的近似最优解，四十多年来，已经取得了令人瞩目的研究进展，其中近似算法研究成果尤为突出。UFL问题，1997年Shmoys等人利用Lin和Vitter的filtering技术以及线性规划取整方法，设计了第一个常数因子近似算法，近似度3.16；此后，Guha和Khuller利用增广贪心技术将Shmoys算法的近似度改进到2.408，同时，在P≠NP的假设下，证明该问题不存在近似度小于1.463的多项式时间算法；1998年，Chudak和Shmoys再次使用线性规划取整方法设计了UFL问题近似度1.736的多项式时间算法：2002年Mahdian等人利用Cost Scaling和增广贪心技术设计了UFL问题目前最好的近似度1.52的多项式时间算法。k-Median问题，1999年Charikar等人利用线性规划技术设计了第一个常数因子近似算法，近似度62／3；同年，Jain和Vazirani利用线性规划和原始对偶方法求解k-median问题获得近似度6的结果，之后Charikar和Guha利用增广贪心技术和Cost Scaling技术进一步将结果改进到4；2001年Arya等人利用启发式局部搜索技术给出k-median问题目前最好的近似度3+ε的多项式时间算法。回顾四十多年的研究历史发现，度量距离空间（Metric）中的两问题近似算法研究是人们关注的焦点，即问题中设施与客户之间连接费用满足三角不等式。然而，现实世界里，两问题的很多应用模型中连接费用并不一定满足上述约束条件，我们称它们为一般距离空间（或非度量空间）中的UFL和k-median问题。惠普公司与英国电信合作研究的通信网络中的动态路由算法就曾经涉及此类问题。相比度量距离空间中的UFL和k-median问题研究成果，一般距离空间中的两问题算法研究工作多年来非常少见。因此，本文主要围绕这类UFL和k-median问题，研究它们的复杂性，设计分析它们的近似算法，给出如下研究成果。（1）我们首先提出了一类一般距离空间中的UFL问题，简称一般UFL问题，即给定问题中客户与设施之间最大连接费用至多是最小连接费用的ω倍，表示为d_max／d_min≤ω。在NP（?）DTIME(n^{O（loglogn）})的假设下，将集合覆盖问题归约到一般UFL问题，利用前者的不可近似性结论，证明满足d_max／d_min≤ω+ε的UFL问题不存在近似性能比小于1.243+0.316ln（ω-1）的多项式时间算法，进而推出，一般UFL问题亦不存在任意常数近似算法；设近似解中设施费用、连接费用与最优解中设施费用、连接费用之比分别为r_f和r_c，证明上述UFL问题不存在多项式时间近似算法使得r_c＜1+（ω-1）·e^-r_f。自1999年Guha等人给出了度量距离空间中的UFL问题算法1.463的不可近似性证明后，一般距离空间中的UFL问题，人们一直渴望见到有关其复杂性的分析报道，但近年来始终未见相关结果出现。我们恰好找到一类特殊的UFL问题，借助它首次严格证明了一般UFL问题算法的不可近似性结果。（2）设计了一般UFL问题局部搜索算法，证明求解d_max／d_min≤ω的UFL问题，算法所得解满足如下关系，L_f+2L_c≤O_f+（1+ω）·O_c，其中L_f，L_c，O_f，O_c分别为局部最优解与全局最优解中的设施费用和连接费用；进而推出，存在1≤α≤2，保证局部搜索算法的近似度为（1+ω）／α。随后，利用实验进一步研究了算法的实际计算效果，统计结果发现，参与实验的所有实例实际求解结果的平均近似度小于1.001；进一步分析实验结果，我们又提出了算法的改进方法。1982年Hochbaum首次研究了一般距离空间中的UFL问题，并设计了平均近似度O（logm）的多项式时间算法，其中m是问题中设施集合中的元素数；2003年Hajiaghayi等人证明一般距离空间中UFL问题依旧属于NP-hard难解问题，并设计了近似度1nm的多项式时间算法。此后一直未见有关这类UFL问题的近似算法研究结果，相比上述一般距离空间中的UFL问题算法，我们的算法在最坏情况下的近似度不随问题实例的规模发生变化。（3）基于给出的一般UFL问题模型，利用其分析方法，建立并分析了一类一般距离空间中的k-median问题，简称一般k-median问题。在NP（?）DTIME(n^{O（loglogn）})的假设下，将集合覆盖问题归约到一般k-median问题，证明d_max／d_min≤ω的k-median问题不存在近似性能比小于1+（ω-1）／e的多项式时间算法，进而推出，一般k-median问题亦不存在任意常数近似算法；进一步研究证明，度量距离空间中的k-median问题不存在近似性能比小于1+2／e的多项式时间算法，除非NP（?）DTIME(n_{O（loglogn）})。关于连接费用任意取值的k-median问题，1992年Lin和Vitter曾经猜测其求解难度同集合覆盖问题一样，并提出证据说它的不可近似性结果极有可能通过对集合覆盖问题归约得出，但他们始终没有给出严格证明。1999年Guha与Khuller曾证明不存在求解度量距离空间中的UFL问题近似性能比小于1.463的多项式时间算法，然而，令人遗憾的是，与它关系最为密切的度量距离空间中的K-median问题不可近似性结果，在本文之前却始终未见相关报道。我们有关k-median问题的复杂性分析填补了多年来这一问题不可近似性理论研究的空白，同时也验证了Lin和Vitter猜想的正确性。（4）给出k-median问题局部搜索算法新的分析方法，证明使用最简单的交换操作，算法求解d_max／d_min≤ω的一般k-median问题时近似度不超过1+（ω-1）／2=（1+ω）／2，时间复杂度O（n）。该结果的出乎意料之处在于算法所能达到的近似度1+（ω-1）／2与反面结果1+（ω-1）／e的形式十分相似；进而推出，对于度量距离空间中的k-median问题，在ω≤5时局部搜索算法的近似度不超过3。我们利用仿真实验研究了k和ω不同取值对算法求解质量的影响，并提出了算法的改进方法。1992年Lin和Vitter率先设计了一般距离空间中的k-median问题多项式时间近似算法，对于任意ε＞0，算法选取（1+1／ε）（lnn+1）k个设施，保证最终解的解值至多是最优解的（1+ε）倍，此后再也未见有关一般k-median问题的算法研究结果。度量距离空间中的k-median问题，2001年Arya等人给出的近似度3+ε局部搜索算法仍是目前最好的结果，但其分析方法对于一般k-median问题已不适用。针对ω≤5的度量距离空间中的k-median问题，本文算法求解它时近似度保证小于3，好于现有3+ε的结果。以上两结果进一步表明，度量距离空间中的k-median问题限制ω≤5的子问题也不存在近似度小于1+2／e的多项式时间算法，但本文所给局部搜索算法可以保证求解该类子问题的近似度不超过3。寻找度量距离空间中的k-median问题近似度不超过3的多项式时间算法一直是众多研究者关注的焦点，但近年来未见任何进展，我们恰好找到它的一类子问题，存在近似度不超过3的多项式近似算法。（5）借鉴集合覆盖问题算法中的思想，设计实现了k-median问题时间复杂度O（nmk）的新贪心算法，其中n和m分别为给定问题中设施集合和客户集合中的元素数。算法的实际计算效果在随后基于ORLIB，SLLIB，GRLIB和TSPLIB测试集的仿真实验中得到了验证。寻求实用有效的k-median问题算法，满足类似QoS路由选择问题的需求，一直是人们的一项重要研究工作。利用Jain和Vazirani的UFL问题算法，Jariyakul曾试图设计k-median问题算法，但他最终发现所得算法实际运行时间较长且计算效果不尽人意；2006年Chrobak等人也曾利用贪心技术设计k-median问题的快速算法，但其算法时间复杂度是O（n³m）。对比性实验结果显示，我们给出的k-median问题新贪心算法无论在求解质量还是运行时间上均明显优于上述两算法。