On Ring Grooming in optical networks

An instance I of Ring Grooming consists of m sets A ₁,A ₂,…, A _m from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P ₁ , P ₂, …,P _k } of {1, 2, …, m} such that for each 1 ≤ i ≤ k and is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition of {1,2,…,m} such that | P _i | ≤ g for each and is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5 when g = 4, at most 2.5 when g = 8, and at most in general while it is conjectured to be at most . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m ^g . Work supported by a DIMACS postdoctoral fellowship.     

Center and Distinguisher for Strings with Unbounded Alphabet

Consider two sets and of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of is a string that minimizes the maximum of Hamming¹ distance(s, s*) over all string s : s . In contrast, a farthest string t* from maximizes the minimum of Hamming distance(t*,t) over all elements t: t . A distinguisher of from is a string that is close to every string in and far away from any string in . We obtain polynomial time approximation schemes to settle the above problems.     

On Approximability of Boolean Formula Minimization

For a Boolean function given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to , or -equivalent to , i.e., . In this paper we prove that if P NP then this problem can not be approximated with a good approximation ratio by a polynomial time algorithm.     

Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.     

Minimum ε-equivalent Circuit Size Problem

For a Boolean function f given by its truth table (of length ) and a parameter s the problem considered is whether there is a Boolean function g -equivalent to f, i.e., , and computed by a circuit of size at most s. In this paper we investigate the complexity of this problem and show that for specific values of it is unlikely to be in P/poly. Under the same assumptions we also consider the optimization variant of the problem and prove its inapproximability.     

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem

We consider the problem of scheduling n jobs withrelease dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of the optimal nonpreemptive schedule to that of the optimal preemptive schedule is at most 7/3, improving a bound of Shmoys and Wein.     

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in time, where is the time to compute the value of f(X) for a subset .     

Domination and total domination in complementary prisms

Let G be a graph and be the complement of G. The complementary prism of G is the graph formed from the disjoint union of G and by adding the edges of a perfect matching between the corresponding vertices of G and . For example, if G is a 5-cycle, then is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, and , where γ(G) and γ _t (G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Inverse Polymatroidal Flow Problem

Let D = (V, A) be a directed graph, for each vertex v V, let ⁺(v) and ^– (v) denote the sets of arcs leaving and entering v, and be intersecting families on ⁺(v) and ^–(v), respectively, and and be submodular functions on intersecting pairs. A flow f : A R is feasible if

Local Optimality and Its Application on Independent Sets for k-claw Free Graphs

Given a graph G = (V,E), we define the locally optimal independent sets asfollows. Let S be an independent set and T be a subset of V such that S T = and (S) T, where (S) is defined as the neighbor set of S. A minimum dominating set of S in T is defined as T_D(S) T such that every vertex of S is adjacent to a vertex inTD(S) and TD(S) has minimum cardinality. An independent setI is called r-locally optimal if it is maximal and there exists noindependent set S V\I with |ID (S)| r such that|S| >|I (S)|.In this paper, we demonstrate that for k-claw free graphs ther-locally optimal independent sets is found in polynomial timeand the worst case is bounded by , where I and I* are a locally optimal and an optimal independent set,respectively. This improves the best published bound by Hochbaum (1983) bynearly a factor of two. The bound is proved by LP duality and complementaryslackness. We provide an efficientO(|V|^r+3) algorithm to find an independent set which is notnecessarily r-locally optimal but is guarantteed with the above bound. Wealso present an algorithm to find a r-locally optimal independent set inO(|V|^r(k-1)+3) time.     

Optimal st-orientations for plane triangulations

For plane triangulations, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G in the st-orientation is (Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). In this paper, we prove the bound is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by . In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height , constructible in linear time, which is also optimal. A preliminary version of this paper was presented at AAIM 2007.     

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 zero error algorithms having oracle access to one query

It is known that (Cai, 2001). The reverse direction of whether ZPP^NP is contained in remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and random string), then it can be simulated in . That is, we prove that . Next we consider whether the above result can be improved as and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPP^NP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ P^NP, settling a long standing open problem. We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely, we prove that . On the other hand, by adapting our proof of our main result it can be shown that . For the purpose of comparing these two results, we prove that . We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2, and . Research supported in part by NSF grant CCR-0208013. A preliminary version of the paper was presented at COCOON′05 Cai and Chakaravarthy (2005). Part of the research was conducted while the author was at the University of Wisconsin, Madison.     

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.     

Paired-domination in generalized claw-free graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.     

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.     

A Probabilistic Analysis of the Capacitated Facility Location Problem

The solution value of a stochastic version of the capacitated facility location problem is studied. It is shown that, for large numbers of customers n, the value of can be closely approximated by , where the constant is identified as a function of the parameters of the underlying stochastic model. Furthermore, an extensive probabilistic analysis is performed on the difference that includes an exponential inequality on the tail distribution, a classification of the speed of convergence and a central limit theorem.     

On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

The problems dealt with in this paper are generalizations of the set cover problem, min{cx | Ax b, x {0,1}ⁿ}, where c Q₊ⁿ, A {0,1}^{m × n}, b 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations.     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices

An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that d_T(i, j) M[i, j] for all i, j and is minimum, where d_T(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + log n), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.