图上若干基本NP难问题的算法研究

本项目主要用计算理论中的新发展起来的分支——参数算法等方法来研究若干基本NP难问题，主要包括：独立集、点覆盖、边支配集、图多分割等问题。项目按照计划全部完成，研究成果超过计划的一倍。项目期间共研获10余个当前最佳的算法等。其中两个基本参数算法被参数计算新闻快报《Parameterized Complexity News》中的Table of Races栏目收录，是该栏目目前收录的仅有两项来自中国的研究结果；在图多分割问题上解决了一个10余年的公开难题；在超图上的多分割研究结果及后续研究在EGRES Open等科学网站上被介绍。项目期间以项目负责人为第一作者在Algorithmica、Theoretical Computer Science、MFCS、ISAAC等国际重要期刊和会议发表学术论文21篇，接收并网上发表论文2篇，其中5篇属于中国计算机协会2013年公布的的B区论文，6篇属于C区论文。另外在投C区以上论文4篇。项目主要取得的研究结果如下： 1. 给出了超图上3块割问题的第一个多项式算法，被EGRES Open网站介绍同时算法被日本京都大学实现，在VLSI上得到应用。 2. 给出了多块割问题一个常用的贪心分而治之算法的的紧致近似率从而解决此问题中的一个10余年的公开问题，同时得到多块割问题目前最好的近似算法。 3. 改进了3度图点覆盖问题和边支配集问题两个基本问题的最佳参数算法，其结果在《Parameterized Complexity News》中的Table of Races栏目中被列出。 4. 改进了低度图上独立集问题的最佳精确算法，基于该结果有望改进1986年Robson给出的一般图上的最佳结果。 5. 在其它图多分割、反馈集、TSP、支配集等问题上给出了8个最佳参数算法、精确算法、核心化算法等。 项目（包括地方人才计划等配套）资助学术交流包括：海外高校访问7人次，参加国际并报告会议13人次，邀请海外专家访问11人次等，国内高校访问8人次。共培养10余本科生和8名硕士研究生。

本项目主要从参数算法、精确算法和近似算法的角度来研究计算机中一些基本的图问题，其中包括被称之为六个基本NP难问题的独立集和点覆盖问题，以及经典的最大流最小割问题的扩展- - 图多分割问题。这些问题非常基础，且应用相当广泛，在整个计算机学科中影响深远，同时这些问题也被研究得非常透彻，任何改进都将在计算机学科内受到强烈关注。项目申请者在这些问题上具有较强的科研基础，近两年研究获得七个当前最优的参数算法、精确算法和近似算法，并解决一个近二十年的公开难题。.参数计算是本项目主要研究方法之一，研究的是一个很难的问题在某个参数较小的时候是否存在有效算法（参数算法）。基于申请人提出的最远最小割技术和新的分支理论，本项目将有望进一步改进并简化图多分割问题的参数算法，3度图及稀疏图上独立集和点覆盖问题的各项算法。在新理论下参数计算中另一个公开难题还有望被解决。目前以上科研进展顺利，预计3年完成。

随着Internet技术的迅猛发展，越来越多的计算逐渐转移到并依赖于Internet这个巨大的计算平台。为了更好地理解Internet，理论计算机科学除了运用传统的逻辑、组合等数学工具外，也开始引入微观经济学以及博弈论的相关知识。本项目正是着眼于由理论计算机领域中的算法和博弈论中的机制设计相结合所产生的新的研究领域- - 算法机制设计中的优化问题。. 本项目将着手刻画收益最优的算法机制的内在组合特性，以及满足不同均衡解的诚实的算法机制的等价条件；并将研究结果应用到广告位置拍卖模型中，设计出公平、合理、实际的收益最优的拍卖机制。. 本项目属于计算机理论科学和经济学中博弈论的交叉学科，是当前国际理论计算机科学界的一个研究热点。本项目扎根于算法设计，研究内容为算法机制设计理论，研究背景为网络广告位置拍卖。其研究结果既可以增进两个学科的融合，又可以推动网络经济的发展。

我们从计算经济学和算法设计等两方面对该项目进行了研究： 1) 我们给出了随机的诚实机制的等价条件。它刻画出了随机的诚实机制的内在的组合特性。该结果能够指导我们设计诚实的机制。 2) 在此基础上，我们给出了一个框架可以将一系列优化问题的近似算法在不改变近似度的前提下，转换成诚实机制，这将有助于我们设计收益最优化的诚实机制。 3) 我们从理论上证明了如果一个竞拍者以多个身份进行拍卖的话，则广义二价拍卖机制将不一定会收敛到一个稳定的状态，甚至不存在一个诚实的而且社会效益最大化的机制。而在目前的现实的广告位置拍卖中，这种现象却屡见不鲜。因此，该研究成果告诉我们在设计拍卖机制的时候，应当严格禁止一个拍卖者以多个身份进行拍卖。 4) 我们提出了弱支配策略删除均衡的概念，并且证明在通用二价拍卖中，在只有两个参与者以及两个广告位的情况下，无论其删除过程怎样，其最终结果几乎满足社会效益最大化。 5) 我们对网络论坛中的帖子的文本内容设计了分析工具，并进行情感分析。该分析能够对股市进行较为准确的分析和预测。我们利用数据挖掘技术对网络论坛对股市进行分析的研究思路和技术可以帮助我们来挖掘广告竞拍者的竞拍行为。 6) 我们研究了世界上最大的B2C市场—eBay下的买家的策略行为，并给出了对称贝叶斯-纳什均衡。我们比较了在此均衡基础上的拍卖商的收益和带有两份拷贝的二价拍卖模型下的拍卖商的收益。我们证明了在绝大多数情况下前者的收益要小于后者的收益。 7) 我们研究了基于约束规划方法的调度问题中不确定信息的建模和求解算法，分析了调度问题中的不确定控制行为，运用定量约束满足问题模型对实时调度问题中的不确定控制行为进行基于定量化策略的建模，在约束求解前进行基于约束一致性验证的可调度性分析，并将其融合到已有的约束求解框架，以提高调度算法和系统的可靠性与可信度。此外，我们还分别研究了行车路线为树和图的情况下的车辆调度问题。我们证明了该优化问题的难解性，并给出了相应的近似算法。 8) 我们研究了二进制串在“与”、“或”、“非”等操作下的判定问题、计数问题和优化问题。评审专家纷纷表示该问题描述简单，结论非常有趣。