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.     

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.     

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.     

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.     

Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals

Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known to for any > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! – O((n – 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.     

Inverse Problems of Matroid Intersection

In this paper we study the inverse problem of matroid intersection: Two matroids M ₁ = (E, ₁) and M ₂ = (E, ₂), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections.     

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.     

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 .     

On Shortest k-Edge-Connected Steiner Networks in Metric Spaces

Given a set of points P in a metric space, let l(P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the shortest k-edge-connected spanning network on P, and let r = inf l(P) P for k 1. In this paper, we show that in any metric space, r 3/4 for k 2, and there exists a polynomial-time -approximation for the shortest k-edge-connected Steiner network, where = 2 for even k and = 2 + 4/(3k) for odd k. In the Euclidean plane, and .     

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.     

Tight Performance Bounds of CP-Scheduling on Out-Trees

The worst-case behavior of the critical path (CP) algorithm for multiprocessor scheduling with an out-tree task dependency structure is studied. The out-tree is not known in advance and the tasks are released on-line over time (each task is released at the completion time of its direct predecessor task in the out-tree). For each task, the processing time and the remainder (the length of the longest chain of the future tasks headed by this task) become known at its release time. The tight worst-case ratio and absolute error are derived for this strongly clairvoyant on-line model. For out-trees with a specific simple structure, essentially better worst-case ratio and absolute error are derived. Our bounds are given in terms of t _max, the length of the longest chain in the out-tree, and it is shown that the worst-case ratio asymptotically approaches 2 for large t _max when the number of processors , where is an integer close to . A non-clairvoyant on-line version (without knowledge of task processing time and remainder at the release time of the task) is also considered and is shown that the worst-case behavior of width-first search is better or the same as that of the depth-first search.     

Fast algorithms for computing the tripartition-based distance between phylogenetic networks

Consider two phylogenetic networks and ’ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by and ’. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an -time algorithm to compute this distance, where h is the number of hybrid nodes in and ’ while k is the maximum number of hybrid nodes among all biconnected components in and ’. Note that $k \ll h \ll n$ in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an $O(n)$-time algorithm for comparing two galled-trees. We also give an -time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively.     

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.     

A {{10}}-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple -approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r _WVC, where r _WVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r _WVC currently stands at . Furthermore we establish that the factor of is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.     

Trivial Two-Stage Group Testing with High Error Rates

Given a population of cardinality q ^r that contains a positive subset P of cardinality p, we give a trivial two-stage method that has first stage pools each of which contains q ^{r – 2} objects. We assume that errors occur in the first stage. We give an algorithm that uses the results of first stage to generate a set CP of candidate positives with |CP| (r + 1)q. We give the expected value of |CPP|. At most (r + 1)q trivial second stage tests are needed to identify all the positives in CP. We assume that the second stage tests are error free.     

Approximation Algorithms for Quadratic Programming

We consider the problem of approximating the global minimum of a general quadratic program (QP) with n variables subject to m ellipsoidal constraints. For m=1, we rigorously show that an -minimizer, where error (0, 1), can be obtained in polynomial time, meaning that the number of arithmetic operations is a polynomial in n, m, and log(1/). For m 2, we present a polynomial-time (1- )-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constraints and the assignment polytope constraints.     

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.     

b-Tree Facets for the Simple Graph Partitioning Polytope

The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each consisting of no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we introduce a large class of facet defining inequalities for the simple graph partitioning polytopes _n (b), b 3, associated with the complete graph on n nodes. These inequalities are induced by a graph configuration which is built upon trees of cardinality b. We provide a closed-form theorem that states all necessary and sufficient conditions for the facet defining property of the inequalities.     

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.     

Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems

We consider Steiner minimum trees (SMT) in the plane, where only orientations with angle , 0 i – 1 and an integer, are allowed. The orientations define a metric, called the orientation metric, , in a natural way. In particular, ₂ metric is the rectilinear metric and the Euclidean metric can beregarded as metric. In this paper, we provide a method to find an optimal SMT for 3 or 4 points by analyzing the topology of SMT's in great details. Utilizing these results and based on the idea of loop detection first proposed in Chao and Hsu, IEEE Trans. CAD, vol. 13, no. 3, pp. 303–309, 1994, we further develop an O(n²) time heuristic for the general SMT problem, including the Euclidean metric. Experiments performed on publicly available benchmark data for 12 different metrics, plus the Euclidean metric, demonstrate the efficiency of our algorithms and the quality of our results.