Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
复制标题
最小化最大加权出度的图方向近似算法
DOI：
10.1007/s10878-009-9276-z
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Kouhei Zenmyo
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Jesper Jansson;Eiji Miyano;Hirotaka Ono;Kouhei Zenmyo
给定一个简单的无向图G=(V,E)和权重函数w:E→ℤ+，我们考虑将所有边定向在E中的问题，以使所有顶点之间的最大加权出度最小化。之前已经表明，问题的未加权版本可以在多项式时间内解决，而加权版本是（弱）NP 困难的。在本文中，我们如下强化了这些结果：（1）我们证明即使所有边权重都属于集合{1,k}（其中k是大于或等于2的任何固定整数），加权版本也是强NP困难的，并且对于这个问题，不存在近似比小于（1+1/k）的伪多项式时间近似算法，除非P = NP； (2) 我们提出了一种新的多项式时间算法，该算法在 (2−1/k) 的比率内近似问题的一般版本，其中 k 是 G 中边的最大权重； (3) 我们展示了如何在多项式时间内近似特殊情况，其中所有边权重都属于 {1,k}，比率为 3/2 fork=2（请注意，这与上面的不可近似性界限相匹配），对于任何 k≥3，分别为 (2−2/(k+1))。
Given a simple, undirected graphG=(V,E) and a weight functionw:E→ℤ+, we consider the problem of orienting all edges inEso that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, wherekis any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), wherekis the maximum weight of an edge inG; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 fork=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for anyk≥3, respectively, in polynomial time.