权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Developing the Algorithm Theory for Combinatorial Optimization based on Hybrid Approaches

发展基于混合方法的组合优化算法理论

基本信息

批准号：
20500009
负责人：
FUJITO Toshihiro
金额：
$ 2.75万
依托单位：
Toyohashi University of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2008
资助国家：
日本
起止时间：
2008 至 2010
项目状态：
已结题

项目摘要

1. The tree cover problem is well studied and known to be approximable within a factor of 2 when given graphs are unweighted, whereas almost nothing is known about its approximability for directed graphs. This study considers the tree cover problem on directed layered graphs, and shows that, while it is Ω(log n) approximation hard, it can be approximated within O(log^<k-1>n) factor for graphs with k layers.2. The independent set problem in graphs is such an NP-hard problem that is known to be hard even to approximate effectively in polynomial time. When graphs are restricted to be d-claw free, while the standard local search heuristic can approximate it within a factor of (d-1+ε)/2(ε>0) in the unweighted case, the best performance guarantee known for general weight instances is due to the Ω(n^d) time d/2-approximation algorithm, or the 2(d-1)/3-approximation algorithm running in polynomial time for any d. Either algorithm is based on the non-standard local search. This study shows the effectiveness of the standard local search for d-claw free instances under constrained weight distributions.3. The multislope ski-rental problem1 is an extension of the classical ski-rental problem. We define the best possible competitive ratio as that of the best strategy for a given instance, and analyze its infimum and supremum over arbitrary instances. It is shown that for the (k+1)-slope problem, the infimum is (k+1)^k/((k+1)^k-k^k), implying that the competitive ratio can be no better than e/(e-1)≒1.58 no matter how many options the player may have. It is also shown that the supremum is 2.47 for k=2 and 2.75 for k=3.

1.树覆盖问题是很好的研究和已知的是在一个因子2的范围内，当给定的图是unweighted，而几乎没有什么是已知的关于它的逼近有向图。本文研究了有向分层图上的树覆盖问题，证明了对于k层图，虽然树覆盖问题的近似困难为Ω（log n），但它可以在O（log^<k-1>n）因子内近似.图中的独立集问题是一个NP难问题，甚至很难在多项式时间内有效地近似。当图被限制为无d-爪时，虽然标准的局部搜索启发式可以在未加权的情况下在（d-1+ε）/2（ε>0）的因子内近似它，但对于一般权重实例已知的最佳性能保证是由于Ω（n^d）时间d/2-近似算法，或者对于任何d在多项式时间内运行的2（d-1）/3-近似算法。这两种算法都是基于非标准的局部搜索。该研究表明了标准局部搜索在约束权重分布下对无d-claw实例的有效性.多坡度滑雪板租赁问题是经典滑雪板租赁问题的推广。我们定义最佳可能的竞争比为给定实例的最佳策略，并分析其下确界和上确界在任意情况下。结果表明，对于（k+1）-斜率问题，下确界为（k+1）^k/（（k+1）^k-k^k），这意味着无论局中人有多少选择，竞争比都不可能优于e/（e-1）<$1.58.它还表明，上确界是2.47为k=2和2.75为k=3。