Developing the Algorithm Theory for Combinatorial Optimization based on Hybrid Approaches

1.树覆盖问题已经得到了很好的研究，当给定的图是无权图时，树覆盖问题在2的因子内是可逼近的，而对于有向图的树覆盖问题几乎没有人知道它的逼近性。本文研究了有向分层图的树覆盖问题，证明了当有向分层图的树覆盖问题是Ω(Logn)逼近困难时，k层图的树覆盖问题可以在O(log^&lt；k-1&gt；n)因子内逼近。图中的独立集问题是一个NP难问题，即使在多项式时间内也很难有效地逼近。当图被限制为无d爪，而标准局部搜索启发式算法在未加权的情况下可以在(d-1+ε)/2(ε&gt；0)的因子内逼近它时，对于一般权值实例已知的最佳性能保证是由于Ω(n^d)时间d/2-近似算法，或对任意d以多项式时间运行的2(d-1)/3-近似算法。该研究表明了标准局部搜索在约束权重分布下对无d爪实例的有效性。多坡道滑雪租赁问题1是经典滑雪租赁问题的延伸。我们将最优竞争比定义为给定实例的最优策略的最佳竞争比，并分析了它在任意实例上的下确界和上确界。结果表明，对于(k+1)-斜率问题，下确界为(k+1)^k/((k+1)^k-k^k)，这意味着无论玩家有多少选择，竞争比都不可能优于e/(e-1)≒1.58。K=2的上确界为2.47，k=3的上确界为2.75。

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.