圈问题是图论、组合优化、运筹学、数理经济学以及理论计算机科学中的重要研究对象。本文的研究围绕旅行商问题和最大覆盖圈包装问题展开。作为最经典的圈问题之一，旅行商问题关注图上经过每个顶点一次且仅一次的最短圈。该问题可嵌入几何空间，成为一个几何化的组合优化问题。最大覆盖圈包装问题则在实际生活中有重要应用价值。其优化目标是找到一组总长度最大的顶点不交(边不交)圈。本文关于旅行商问题的研究关注其在曲面距离空间内的性质，而对最大覆盖圈包装问题则以其子问题——制服调换问题及变异问题——肾脏调换问题为主要研究对象。主要内容如下：1.在一般的距离空间内，旅行商问题仅存在近似比为常数的近似算法。而在欧氏空间内，该问题存在多项式时间近似方案。其近似方案所使用的“递归剖分+动态规划”的方法已成功应用到一系列的组合优化问题。为探索导致旅行商问题可近似性巨大变化的具体原因，也为进一步拓展“递归剖分+动态规划”方法的适用范围，研究曲面上的旅行商问题。首先证明了球面不可递归正则剖分，表明平面上的算法过程无法直接应用到球面上。接着利用球面与其内接平面之间射影的有限形变特征，将球面旅行商问题实例射影到平面，递归剖分之后连同剖分网格再次射影到球面，在球面上进行动态规划，从而得到了球面旅行商问题的多项式时间近似方案。最后将上述结论推广到一大类曲面上。2. BHH定理表明随机旅行商问题存在一个重要特征：旅行商问题常数。其直觉基础是均匀随机旅行商问题最优环游的自相似性。球面的对称性较平面更加完美，因此尝试证明球面旅行商问题常数的存在性。BHH定理的现有证明均依赖于欧氏空间的可线性缩放性，而球面无此性质。文中构造了一族渐次逼近球面的球内接多面体，证明了每个此类多面体的表面上旅行商问题常数存在且与平面旅行商问题常数相等，继而取极限将该结论拓展到球面及一些其它曲面。3.作为最大覆盖圈包装问题的一个子问题，以物易物制服调换问题继承了其O(n3)时间可解性。通过将需要同型号制服且持有同型号制服的人看作一个等价类的方法，将最大覆盖圈包装转化为常量阶有向图上的顶点容量约束整值最大环流，从而得到了以物易物制服调换问题的一个Θ(n)时间算法。最大环流可行域整性的证明进一步增强了该算法的实用性。4.为进一步缓解待移植肾脏严重短缺的状况，将肾脏调换问题的博弈模型推广到多捐赠者情形。分析了多捐赠者肾脏调换博弈可行解及稳定解的结构，证明了无法以同时捐赠多颗肾脏来换取参与稳定调换，将TTC算法、肾脏调换博弈稳定解的NP难解性以及最大覆盖稳定解的不可近似性拓展到新模型。实验表明这一推广可有效提高病人得到匹配肾脏的可能性。