Developing the Algorithm Theory for Combinatorial Optimization based on Hybrid Approaches

1. 树覆盖问题已经得到了很好的研究，并且已知当给定的图没有加权时，它在2因子内是近似的，而对于有向图，它的近似性几乎一无所知。本研究考虑了有向分层图上的树覆盖问题，结果表明，虽然该问题很难近似Ω（log n），但对于有k层的图，它可以在O（log^<k-1>n）因子内近似。图中的独立集问题是一个np困难问题，它甚至很难在多项式时间内有效地逼近。当图被限制为无d爪时，而标准局部搜索启发式可以在未加权情况下在因子(d-1+ε)/2（ε>0）内近似它，对于一般权重实例而言，已知的最佳性能保证是由于Ω（n^d）时间d/2近似算法，或2(d-1)/3近似算法在多项式时间内运行任何d。任一算法都是基于非标准局部搜索。本研究证明了在约束权分布下，标准局部搜索d爪自由实例的有效性。多坡滑雪板租赁问题是经典滑雪板租赁问题的延伸。我们将最佳可能竞争比定义为给定实例的最佳策略的竞争比，并分析其在任意实例上的最小值和最优值。结果表明，对于（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.