Node-weighted Steiner tree approximation in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n ^O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.     

Separating sublinear time computations by approximate diameter

We study the problem of separating sublinear time computations via approximating the diameter for a sequence S=p ₁ p ₂ ⋅⋅⋅ p _n of points in a metric space, in which any two consecutive points have the same distance. The computation is considered respectively under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations using various versions of the approximate diameter problem based on restrictions on input data. We derive tight sublinear time separations for each of the three computation models via proving that computation with O(n ^r ) time is strictly more powerful than that with O(n ^r−ε ) time, where r and ε are arbitrary parameters in (0,1) and (0,r) respectively. We show that, for any parameter r∈(0,1), the bounded error randomized sublinear time computation in time O(n ^r ) cannot be simulated by any zero error randomized sublinear time algorithm in o(n) time or queries; and the same is true for zero error randomized computation versus deterministic computation.     

Minimum entropy coloring

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky (IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem. S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal. G. Joret is a F.R.S.-FNRS Research Fellow.     

A combinatorial theorem on labeling squares with points and its application

In this paper, we present a combinatorial theorem on labeling disjoint axis-parallel squares of edge length two using points. Given an arbitrary set of disjoint axis-parallel squares of edge length two, we show that if we label points on the boundary of all squares (one for each square) and define a distance label graph such that there is an edge between any two labeling points if and only if their L_∞-distance is at most 1 − ε (0 < ε < 1), then the maximum connected component of the graph contains Θ(1/ε) vertices, which is tight. With this theorem we present a new and simple factor-(3 + ε) approximation for labeling points with axis-parallel squares under the slider model. This research is supported by NSF CARGO Grant DMS-0138065.     

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.     

Polynomial time approximation schemes for minimum disk cover problems

The following planar minimum disk cover problem is considered in this paper: given a set D\mathcal{D} of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within a factor of (1+ε) in O(mn^{O(\frac1e2log2\frac1e)})\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})}) time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem are considered and approximation schemes are designed.     

Hardness and algorithms for rainbow connection

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In the first result of this paper we prove that computing rc(G) is NP-Hard solving an open problem from Caro et al. (Electron. J. Comb. 15, 2008, Paper R57). In fact, we prove that it is already NP-Complete to decide if rc(G)=2, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every ε>0, a connected graph with minimum degree at least ε n has bounded rainbow connection, where the bound depends only on ε, and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.     

Optimal tree structure with loyal users and batch updates

We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(n⋅K+K ⁴) time where K=min {4(log (1−p)⁻¹)⁻¹,n} and n is the number of normal users.     

Finding longest increasing and common subsequences in streaming data

We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet αbet has length at least k, we discuss a one-pass algorithm using O(k log αbetsize) space, with update time either O(log k) or O(log log αbetsize); for αbetsize = O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of Ω(k) on the space requirement for this problem for general alphabets αbet, even when the input stream is a permutation of αbet. For finding the actual LIS, we give a ⌈log (1 + 1/ɛ)-pass algorithm using O(k^1+ɛlog αbetsize) space, for any ɛ > 0. For LCS, there is a trivial Θ(1)-approximate O(log n)-space streaming algorithm when αbetsize = O(1). For general alphabets αbet, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it is necessary to use Ω(n/ρ²) space to approximate the LCS of two n-element streams to within a factor of ρ, even if the streams are permutations of each other. A preliminary version of this paper appears in the Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05), August 2005, pp. 263–272.     

A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time

We study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k³(n+k)^k−1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(n^k−m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n^k−m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. The preliminary version of this paper appeared in Proceedings of the 11th Annual International Computing and Combinatorics Conference as “Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling”.     

Alignments with non-overlapping moves,inversions and tandem duplications in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) time

Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in O(n ³) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n ⁵) for general scoring schemes, O(n ⁴log n) for concave scoring schemes and O(n ⁴) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 151–164.     

Approximation algorithms for multicast routing in ad hoc wireless networks

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.     

Inapproximability results for the lateral gene transfer problem

This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following:

Inapproximability and approximability of maximal tree routing and coloring

Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability of this problem and prove Ω(g^1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds. Supported in part by the NSF of China under Grant No. 70221001 and 60373012.     

Point sets in the unit square and large areas of convex hulls of subsets of points

In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]² are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n ^6k−4) time algorithm is given, which finds distributions of n points in [0,1]² such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)^1/(j−2)/n ^{(j−1)/(j−2)}).     

Tree edge decomposition with an application to minimum ultrametric tree approximation

A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.     

Packing trees in communication networks

Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size. This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths. A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship for the fourth author.     

Improved algorithms for largest cardinality 2-interval pattern problem

The 2-INTERVAL PATTERN problem is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are R-comparable, where model . The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an O(n{log} n +L) algorithm is proposed for the case , where is the total length of all 2-intervals (density d is the maximum number of 2-intervals over any point). This improves previous O(n ²log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n ²) result. Finally, we present another algorithm for the case with disjoint support(interval ground set), which improves previous O(n ²□n) upper bound. A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005.     

Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults

The locally twisted cube is a variation of hypercube, which possesses some properties superior to the hypercube. In this paper, we investigate the edge-fault-tolerant hamiltonicity of an n-dimensional locally twisted cube, denoted by LTQ _n . We show that for any LTQ _n (n≥3) with at most 2n−5 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. We also demonstrate that our result is optimal with respect to the number of faulty edges tolerated.     

On the Bandpass problem

The complexity of the Bandpass problem is re-investigated. Specifically, we show that the problem with any fixed bandpass number B≥2 is NP-hard. Next, a row stacking algorithm is proposed for the problem with three columns, which produces a solution that is at most 1 less than the optimum. For the special case B=2, the row stacking algorithm guarantees an optimal solution. On approximation, for the general problem, we present an O(B ²)-algorithm, which reduces to a 2-approximation algorithm for the special case B=2.