Power Assignment for <Emphasis Type="Italic">k</Emphasis>-Connectivity in Wireless Ad Hoc Networks

The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k, a (k + 12H (k)) -approximation algorithm for k(2k–1) n where n is the network size, a (k+2(k + 1)/2) -approximation algorithm for 2 k7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.This work is supported in part by Hong Kong Research Grant Council under grant No. CityU 1149/04E.This work is partially supported by NSF CCR-0311174.     

On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function

The problem of colouring a k-colourable graph is well-known to be NP-complete, for k 3. The MAX-k-CUT approach to approximate k-colouring is to assign k colours to all of the vertices in polynomial time such that the fraction of `defect edges' (with endpoints of the same colour) is provably small. The best known approximation was obtained by Frieze and Jerrum (1997), using a semidefinite programming (SDP) relaxation which is related to the Lovász -function. In a related work, Karger et al. (1998) devised approximation algorithms for colouring k-colourable graphs exactly in polynomial time with as few colours as possible. They also used an SDP relaxation related to the -function.In this paper we further explore semidefinite programming relaxations where graph colouring is viewed as a satisfiability problem, as considered in De Klerk et al. (2000). We first show that the approximation to the chromatic number suggested in De Klerk et al. (2000) is bounded from above by the Lovász -function. The underlying semidefinite programming relaxation in De Klerk et al. (2000) involves a lifting of the approximation space, which in turn suggests a provably good MAX-k-CUT algorithm. We show that of our algorithm is closely related to that of Frieze and Jerrum; thus we can sharpen their approximation guarantees for MAX-k-CUT for small fixed values of k. For example, if k = 3 we can improve their bound from 0.832718 to 0.836008, and for k = 4 from 0.850301 to 0.857487. We also give a new asymptotic analysis of the Frieze-Jerrum rounding scheme, that provides a unifying proof of the main results of both Frieze and Jerrum (1997) and Karger et al. (1998) for k 0.     

Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition

The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E, w) is well-studied. In this paper, we present fast (sequential linear time and parallel logarithmic time) on-line algorithms for optimally reinforcing the graph when the reinforcement material is available continuously on-line. These are the first on-line algorithms for this problem. We invest O(|V|³|E|log|V|) time (equivalent to (|V|) invocations of the fastest known algorithms for optimal reinforcement) in preprocessing the graph before the start of our algorithms. It is shown that the output of our on-line algorithms is as good as that of the off-line algorithms. Thus our algorithms are better than the fastest off-line algorithms in situations when a sequence of more than (|V|) reinforcement problems need to be solved. The key idea is to make use of ideas underlying the theory of Principal Partition of a Graph. Our ideas are easily generalized to the general setting of polymatroid functions. We also present a new efficient algorithm for computation of the Principal Sequence of a graph.     

New Approximation Algorithms for Map Labeling with Sliding Labels

In this paper we present approximation algorithm for the following NP-hard map labeling problem: Given a set S of n distinct sites in the plane, one needs to place at each site a uniform square of maximum possible size such that all the squares are along the same direction. This generalizes the classical problem of labeling points with axis-parallel squares and restricts the most general version where the squares can have different orientations. We obtain factor-4 and factor- approximation algorithms for this problem. These algorithms also work for two generalized versions of the problem. We also revisit the problem of labeling each point with maximum uniform axis-parallel square pairs and improve the previous approximation factor of 4 to 3.     

Approximation Algorithms for Bounded Facility Location Problems

The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.     

A solution to a conjecture on the generalized connectivity of graphs

The generalized k-connectivity \(\kappa _k(G)\) of a graph G was introduced by Chartrand et al. in (Bull Bombay Math Colloq 2:1–6, 1984), which is a nice generalization of the classical connectivity. Recently, as a natural counterpart, Li et al. proposed the concept of generalized edge-connectivity for a graph. In this paper, we consider the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. We give a confirmative solution to a conjecture raised by S. Li in Ph.D. Thesis (2012). We also give a polynomial-time algorithm to a problem of generalized k-edge-connectivity.     

New algorithms for online rectangle filling with <Emphasis Type="BoldItalic">k</Emphasis>-lookahead

We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present deterministic and randomized results for algorithms that are allowed a k-lookahead for k≥2. Our main result is a deterministic min {1.848,1+2/(k−1)}-competitive online algorithm. This is the first algorithm for this problem with a competitive ratio approaching 1 as k approaches +∞. The previous best-known solution for this problem has a competitive ratio of 2 for any k≥2. We also present a randomized online algorithm with a competitive ratio of 1+1/(k+1). Our final result is a closely matching lower bound (also proved in this paper) of $1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2))$1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2)) on the competitive ratio of any randomized online algorithm against an oblivious adversary. These are the first known results for randomized algorithms for this problem.     

Online leasing problem with price fluctuations under the consumer price index

We present a \((20+{5}/{n})\)-approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal–dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.     

Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of . This is an improvement over the ratio of attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of for this problem, where k 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of for this problem.     

An approximation algorithm for <Emphasis Type="Italic">k</Emphasis>-facility location problem with linear penalties using local search scheme

In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is \(2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon \), where \(p \in {\mathbb {Z}}_+\) is a parameter of the algorithm and \(\epsilon >0\) is a positive number.     

Average-Case Performance Analysis of a 2D Strip Packing Algorithm—NFDH

The two-dimensional strip packing problem is a generalization of the classic one-dimensional bin packing problem. It has many important applications such as costume clipping, material cutting, real-world planning, packing, scheduling etc. Average-case performance analysis of approximation algorithms attracts a lot of attention because it plays a crucial role in selecting an appropriate algorithm for a given application. While approximation algorithms for two-dimensional packing are frequently presented, the results of their average-case performance analyses have seldom been reported due to intractability. In this paper, we analyze the average-case performance of Next Fit Decreasing Height (NFDH) algorithm, one of the first strip packing algorithms proposed by Coffman, Jr. in 1980. We prove that the expected height of packing with NFDH algorithm, when the heights and widths of the rectangle items are independent and both obey (0, 1] uniform distribution, is about n/3, where n is the number of rectangle items. We also validate the theoretical result with experiments.This work is supported by National 973 Fundamental Research Project of China on NP Complete Problems and High Performance Software (No. G1998030403).     

On the Tightness of the Alternating-Cycle Lower Bound for Sorting by Reversals

We give a theoretical answer to a natural question arising from a few years of computational experiments on the problem of sorting a permutation by the minimum number of reversals, which has relevant applications in computational molecular biology. The experiments carried out on the problem showed that the so-called alternating-cycle lower bound is equal to the optimal solution value in almost all cases, and this is the main reason why the state-of-the-art algorithms for the problem are quite effective in practice. Since worst-case analysis cannot give an adequate justification for this observation, we focus our attention on estimating the probability that, for a random permutation of n elements, the above lower bound is not tight. We show that this probability is low even for small n, and asymptotically (1/n⁵), i.e., O(1/n⁵) and (1/n⁵). This gives a satisfactory explanation to empirical observations and shows that the problem of sorting by reversals and its alternating-cycle relaxation are essentially the same problem, with the exception of a small fraction of pathological instances, justifying the use of algorithms which are heavily based on this relaxation. From our analysis we obtain convenient sufficient conditions to test if the alternating-cycle lower bound is tight for a given instance. We also consider the case of signed permutations, for which the analysis is much simpler, and show that the probability that the alternating-cycle lower bound is not tight for a random signed permutation of m elements is asymptotically (1/m²).     

FPT algorithms for Connected Feedback Vertex Set

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F?V, |F|??k, such that G[V?F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 ^O(k) n ^O(1)) on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.     

Construction of the nearest neighbor embracing graph of a point set

This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph can also be used as a tool to test whether a point set is randomly generated or has some particular properties. We show that in 2-D the NNE-graph can be constructed in optimal time in the worst case. We also present an time algorithm, where d is the -th largest degree in the utput NNE-graph. The algorithm is optimal when . The algorithm is also sensitive to the structure of the NNE-graph, for instance when , the number of edges in NNE-graph is bounded by for any value g with . We finally propose an time algorithm for the problem in 3-D, where d and are the -th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the largest vertex degree of the NNE-graph is .     

On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time

Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C _j is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time w _j C _j. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + )-competitive on-line algorithm for any > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.     

Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F ₁?F ₂?????F _n , where each F _k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F _k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, 2007), we obtain the competitive ratio \(16+8\sqrt{3}+\epsilon\). The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8α?1.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

Flows with unit path capacities and related packing and covering problems

Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log?m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an O(?m)O(\sqrt{m}) -approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.