Distance-d independent set problems for bipartite and chordal graphs

The paper studies a generalization of the Independent Set problem (IS for short). A distance- $d$ independent set for an integer $d\ge 2$ in an unweighted graph $G = (V, E)$ is a subset $S\subseteq V$ of vertices such that for any pair of vertices $u, v \in S$ , the distance between $u$ and $v$ is at least $d$ in $G$ . Given an unweighted graph $G$ and a positive integer $k$ , the Distance- $d$ Independent Set problem (D $d$ IS for short) is to decide whether $G$ contains a distance- $d$ independent set $S$ such that $|S| \ge k$ . D2IS is identical to the original IS. Thus D2IS is $\mathcal{NP}$ -complete even for planar graphs, but it is in $\mathcal{P}$ for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D $d$ IS, its maximization version MaxD $d$ IS, and its parameterized version ParaD $d$ IS( $k$ ), where the parameter is the size of the distance- $d$ independent set: (1) We first prove that for any $\varepsilon >0$ and any fixed integer $d\ge 3$ , it is $\mathcal{NP}$ -hard to approximate MaxD $d$ IS to within a factor of $n^{1/2-\varepsilon }$ for bipartite graphs of $n$ vertices, and for any fixed integer $d\ge 3$ , ParaD $d$ IS( $k$ ) is $\mathcal{W}[1]$ -hard for bipartite graphs. Then, (2) we prove that for every fixed integer $d\ge 3$ , D $d$ IS remains $\mathcal{NP}$ -complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D $d$ IS can be solved in polynomial time for any even $d\ge 2$ , whereas D $d$ IS is $\mathcal{NP}$ -complete for any odd $d\ge 3$ . Also, we show the hardness of approximation of MaxD $d$ IS and the $\mathcal{W}[1]$ -hardness of ParaD $d$ IS( $k$ ) on chordal graphs for any odd $d\ge 3$ .     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so 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}, where k is 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), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

(1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation

This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270–281, 2004). We propose a (1+1/α)-competitive algorithm with help of (1+?α?)lg^? h trees for the height h of the OVSF code tree and any α≥1. In other words, it is a (1+ε)-competitive algorithm with help of (1+?1/ε?)lg^? h trees for any constant 0<ε≤1. In the case of α=1 (or ε=1), we obtain a 2-competitive algorithm with 2lg^? h trees, which substantially improves the previous resource of 3h/8+2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+δ)-competitive algorithm with (11/4+4/(3δ)) trees for any 0<δ≤4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when α≥3 (or ε≤1/3), although the incurred cost for individual requests is bounded to a constant.     

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.