Search

Given a directed graph G=(V, E) and an integer k ≥ 1, a k-transitive-closure spanner (k-TC-spanner) of G is a directed graph H=(V, E H ) that has (1) the same transitive closure as G and (2) diameter at most k. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner). Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TC-spanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding. We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d- dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with small Lipschitz constant. The lower bound is derived from an explicit dual solution to a linear programming relaxation of the Steiner 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a lower bound on the size of Steiner k-TC-spanners of d-dimensional posets. It shows that the best-known construction, due to De Santis et al., cannot be improved significantly.

Economic forces, driven by the desire to introduce flash into the high-end storage market without changing existing software-base, have resulted in the emergence of solid-state drives (SSDs), flash packaged in HDD form factors and capable of working with device drivers and I/O buses designed for HDDs. Unlike the use of DRAM for caching or buffering, however, certain idiosyncrasies of NAND Flash-based solid-state drives (SSDs) make their integration into hard disk drive (HDD)-based storage systems nontrivial. Flash memory suffers from limits on its reliability, is an order of magnitude more expensive than the magnetic hard disk drives (HDDs), and can sometimes be as slow as the HDD (due to excessive garbage collection (GC) induced by high intensity of random writes). Given the complementary properties of HDDs and SSDs in terms of cost, performance, and lifetime, the current consensus among several storage experts is to view SSDs not as a replacement for HDD, but rather as a complementary device within the high-performance storage hierarchy. Thus, we design and evaluate such a hybrid storage system with HybridPlan that is an improved capacity planning technique to administrators with the overall goal of operating within cost-budgets. HybridPlan is able to find the most cost-effective hybrid storage configuration with different types of SSDs and HDDs

We present an O(nlogn)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G=(V,E) with nonnegative edge lengths d:E->R^>=^0 and a stretchk>=1, a subgraph H=(V,E"H) is a k-spanner of G if for every edge (s,t)@?E, the graph H contains a path from s to t of length at most [email protected]?d(s,t). The previous best approximation ratio was [email protected]?(n^2^/^3), due to Dinitz and Krauthgamer (STOC @?11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from [email protected]?(n) to O(n^1^/^3logn). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS @?10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and [email protected]?s lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O(n^1^/^3logn)-approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O(n)-approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O(n^2^/^3^+^@e) for any constant @e>0, which improves the O(n^@[email protected]?min(n^4^/^5,m^2^/^3)) ratio due to Feldman, Kortsarz and Nutov ([email protected]?12).

In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results; this is done by directly transforming the inapproximability gap of Haastad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or., 25 pages

The topology of $\beta$-sheets is defined by the pattern of hydrogen-bonded strand pairing. Therefore, predicting hydrogen bonded strand partners is a fundamental step towards predicting $\beta$-sheet topology. At the same time, finding the correct partners is very difficult due to long range interactions involved in strand pairing. Additionally, patterns of aminoacids involved, in $\beta$-sheet formations are very general and therefore difficult to use for computational recognition of specific contacts between strands. In this work, we report a new strand pairing algorithm. To address above mentioned difficulties, our algorithm attempts to mimic elements of the folding process. Namely, in addition to ensuring that the predicted hydrogen bonded strand pairs satisfy basic global consistency constraints, it takes into account hypothetical folding pathways. Consistently with this view, introducing hydrogen bonds between a pair of strands changes the probabilities of forming hydrogen bonds between other pairs of strand. We demonstrate that this approach provides an improvement over previously proposed algorithms. We also compare the performance of this method to that of a global optimization algorithm that poses the problem as integer linear programming optimization problem and solves it using ILOG CPLEX\texttrademark\ package.

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every set in S and a "coverage factor" (positive integer) k. A subset of elements are presented online in an arbitrary order. When each element, say i, is presented, we are also told the collection of all (at least k) sets and their costs to which i belongs and we need to select additional sets from these sets containing i, if necessary, such that our collection of selected sets contains at least k sets that contain the element i. The goal is to minimize the total cost of the selected sets (our algorithm and competitive ratio bounds can be extended to the case when a set can be selected at most a pre-specified number of times instead of just once; we do not report these extensions for simplicity and also because they have no relevance to the biological applications that motivated our work). In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of Littlestone. This algorithm generalizes and improves some earlier results by N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. We also discuss lower bounds on competitive ratios for deterministic algorithms for general $k$., Comment: 22 pages

We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter $${\epsilon }\in (0,1/2)$$ , a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is $${\epsilon }$$ -far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only $$O({\epsilon }^{-1})$$ samples. In contrast, we prove that convexity can be tested with $$O({\epsilon }^{-1})$$ queries by testers that can make queries of their choice while uniform testers for this property require $$\varOmega ({\epsilon }^{-5/4})$$ samples. Previously, the fastest known tester for convexity needed $$\varTheta ({\epsilon }^{-4/3})$$ queries.

We consider the following basic geometric problem: Given epsilon in (0,1/2), a 2-dimensional figure that consists of a black object and a white background is epsilon-far from convex if it differs in at least an epsilon fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is epsilon-far from convex are needed to detect a violation of convexity with probability at least 2/3? This question arises in the context of designing property testers for convexity. Specifically, a (1-sided error) tester for convexity gets samples from the figure, labeled by their color; it always accepts if the black object is convex; it rejects with probability at least 2/3 if the figure is epsilon-far from convex. We show that Theta(epsilon^{-4/3}) uniform samples are necessary and sufficient for detecting a violation of convexity in an epsilon-far figure and, equivalently, for testing convexity of figures with 1-sided error. Our testing algorithm runs in time O(epsilon^{-4/3}) and thus beats the Omega(epsilon^{-3/2}) sample lower bound for learning convex figures under the uniform distribution from the work of Schmeltz (Data Structures and Efficient Algorithms,1992). It shows that, with uniform samples, we can check if a set is approximately convex much faster than we can find an approximate representation of a convex set.

Computing a suitable measure of consensus among several clusterings on the same data is an important problem that arises in several areas such as computational biology and data mining. In this paper, we formalize a set-theoretic model for computing such a similarity measure. Roughly speaking, in this model we have k >1 partitions (clusters) of the same data set each containing the same number of sets and the goal is to align the sets in each partition to minimize a similarity measure. For k=2, a polynomial-time solution was proposed by Gusfield (Information Processing Letters 82 (2002) 159-164). In this paper, we show that the problem is MAX-SNP-hard for k=3 even if each partition in each cluster contains no more than 2 elements and provide a -approximation algorithm for the problem for any k.

In this paper we investigate the inverse protein folding (IPF) problem under the Canonical model on 3D and 2D lattices [W.E. Hart, On the computational complexity of sequence design problems, Proceedings of the First Annual International Conference on Computational Molecular Biology 1997, pp. 128–136; E.I. Shakhnovich, A.M. Gutin, Engineering of stable and fast-folding sequences of model proteins, Proc. Natl. Acad. Sci. 90 (1993) 7195–7199]. In this problem, we are given a contact graph G=(V,E) of a protein sequence that is embeddable in a 3D (respectively, 2D) lattice and an integer 1⩽K⩽|V|. The goal is to find an induced subgraph of G of at most K vertices with the maximum number of edges. In this paper, we prove the following results:•An earlier proof of NP-completeness of the IPF problem on 3D lattices [W.E. Hart, On the computational complexity of sequence design problems, Proceedings of the First Annual International Conference on Computational Molecular Biology 1997, pp. 128–136] is based on the NP-completeness of the IPF problem on the 2D lattices. However, the reduction was not correct and we show that the IPF problem for 2D lattices can be solved in O(K|V|) time. But, we show that the IPF problem on 3D lattices is indeed NP-complete by a providing a different reduction from a different NP-complete problem.•We design a polynomial-time approximation scheme for the IPF problem on 3D lattices using the shifted slice-and-dice approach in [P. Berman, B. DasGupta, S. Muthukrishnan, Approximation algorithms for MAX-MIN tiling, J. Algorithms 47(2) (2003) 122–134; D. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, MA, 1997; D.S. Hochbaum, W. Mass, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM 32(1) (1985) 130–136], thereby improving the previous best polynomial-time approximation algorithm which had a performance ratio of 12 [W.E. Hart, On the computational complexity of sequence design problems, Proceedings of the First Annual International Conference on Computational Molecular Biology 1997, pp. 128–136].

In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished” by a family of “tests”, and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of “basic” tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem. We conclude by reporting preliminary computational results on the implementations of our algorithmic approaches for the minimum cost probe set problems on a data set used by Borneman et al.

In this paper, we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size-bound parameters, we want to find a set of tiles of maximum total weight such that each tiles satisfies the size bounds. A solution to this problem is important to a number of computational biology applications such as selecting genomic DNA fragments for PCR-based amplicon microarrays and performing homology searches with long sequence queries. Our goal is to design efficient algorithms with linear or near-linear time and space in the normal range of parameter values for these problems. For this purpose, we first discuss the solution to a basic online interval maximum problem via a sliding-window approach and show how to use this solution in a nontrivial manner for many of the tiling problems introduced. We also discuss NP-hardness results and approximation algorithms for generalizing our basic tiling problem to higher dimensions. Finally, computational results from applying our tiling algorithms to genomic sequences of five model eukaryotes are reported.

We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property (that is, the smallest fraction of pixels that need to change in the image to ensure that the image satisfies the desired property). Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise. Prior to this work, only one tolerant testing algorithm for an image property (image partitioning) has been published. We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so that it becomes a half-plane? a representation of a convex object? a representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error epsilon, after reading a number of pixels polynomial in 1/epsilon and independent of the size of the image. The running time of the testers for half-plane and convexity is also polynomial in 1/epsilon. Tolerant testers for these three properties were not investigated previously. For convexity and connectedness, even the existence of distance approximation algorithms with query complexity independent of the input size is not implied by previous work. (It does not follow from the VC-dimension bounds, since VC dimension of convexity and connectedness, even in two dimensions, depends on the input size. It also does not follow from the existence of non-tolerant testers.) Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons P_{epsilon} such that (1) every convex image has a nearby polygon in P_{epsilon} and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in P_{epsilon}. This construction might be of independent interest.

We consider the complexity of problems related to two-dimensional texts (2D-texts) described succinctly. In a succinct description, larger rectangular subtexts are defined in terms of smaller parts in a way similar to that of Lempel–Ziv compression for 1D-texts, or in strings with shortened descriptions as in ( Nordic J. Comput. 4 (1997) 172–186), or in hierarchical graphs described by context-free graph grammars. A given 2D-text T with many internal repetitions can have a hierarchical description which may be exponentially smaller and which can be given as an input for a pattern-matching algorithm which gives information about T . Such a hierarchical description is given in terms of a straight-line program, or SLP (see Nordic J. Comput. 4 (1997) 172–186) or, equivalently, of a 2D grammar. We consider compressed pattern matching , where the input consists of a 2D-pattern P and a hierarchical description of a 2D-text T , and fully compressed pattern matching , where the input consists of hierarchical descriptions of both the pattern P and the text T . For 1D strings, there exist polynomial-time deterministic algorithms for these problems for similar types of succinct text descriptions ( J. Comput. System Sci. 52 (2) (1996) 299–307; “Proceedings of the 27th Annual Symposium on the Theory of Computing,” pp. 703–712; “Proceedings of the 5th Scandinavian Workshop on Algorithm Theory,” Springer-Verlag, Berlin, 1996; Nordic J. Comput. 4 (2) (1997), 172–186). We show that the complexity dramatically increases in a 2D setting. For example, compressed 2D-matching is NP -complete, fully compressed 2D-matching is Σ P 2 -complete, and testing a given occurrence of a 2D compressed pattern is co- NP -complete. On the other hand, we give efficient algorithms for the related problems of randomized equality testing and testing for a given occurrence of an uncompressed pattern. We also show the surprising fact that the compressed size of a subrectangle of a compressed 2D array can grow exponentially, unlike the 1D case.

We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: An upper bound of 3n-1 in general, and an upper bound of 2n-1 if the rectangles tile the underlying space. This improves the upper bounds of 4n in [V. Hai Nguyen and P. Widmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255--259]. A BSP satisfying the upper bounds can be constructed in O(n log n) time. A worst-case lower bound of 2n-o(n) in general, and $\frac{3n}{2}-o(n)$ if the rectangles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of $\frac{4}{3}$ or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees.

Motivation: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments. Results: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment’s length. Practical applications to alignments of genomic DNA sequences are described. Availability: Software is available at http://globin.cse.psu.edu/ Contact: webb@cse.psu.edu

A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. The problem considered is that of finding a minimum feedback vertex set given a weighted and undirected graph. We present a simple and efficient approximation algorithm with performance ratio of at most 2, improving previous best bounds for either weighted or unweighted cases of the problem. Any further improvement on this bound, matching the best constant factor known for the vertex cover problem, is deemed challenging. The approximation principle, underlying the algorithm, is based on a generalized form of the classical local ratio theorem, originally developed for approximation of the vertex cover problem, and a more flexible style of its application.

We present a parallel algorithm for the Voronoi diagram of the set of vertices of a convex polygon. The algorithm runs in time O(log n) and uses O(n log log nlog n) processors in the CRCW PRAM model. The concurrent write is used only by an integer sorting subroutine. We also obtain an O(log n)-time and O(n log log nlog n)-processor CRCW PRAM algorithm for the construction of the medial axis of a convex polygon. Our algorithms use the solution to the duration-unknown task scheduling problem due to Cole and Vishkin and the optimal parallel algorithm for the convex hull of a polygon due to Wagener. They are randomized in the sense that for any given l > 0 they terminate in time O(log n) with probability greater than 1 − n−1.

Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable emphasis is placed on the analyzing the cause and effect of such threats. The financial crisis in the current and past decade has shown that one important cause of instability in global markets is the so-called financial contagion, namely the spreading of instabilities or failures of individual components of the network to other, perhaps healthier, components. This leads to a natural question of whether the regulatory authorities could have predicted and perhaps mitigated the current economic crisis by effective computations of some stability measure of the banking networks. Motivated by such observations, we consider the problem of defining and evaluating stabilities of both homogeneous and heterogeneous banking networks against propagation of synchronous idiosyncratic shocks given to a subset of banks. We formalize the homogeneous banking network model of Nier et al. and its corresponding heterogeneous version, formalize the synchronous shock propagation procedures, define two appropriate stability measures and investigate the computational complexities of evaluating these measures for various network topologies and parameters of interest. Our results and proofs also shed some light on the properties of topologies and parameters of the network that may lead to higher or lower stabilities., Comment: to appear in Algorithmica

Unlike the use of DRAM for caching or buffering, certain idiosyncrasies of SSDs make their integration into existing systems non-trivial. Flash memory suffers from limits on its reliability, is an order of magnitude more expensive than the HDD, and can sometimes be as slow as the HDD (due to excessive garbage collection (GC) induced by high intensity of random writes). Given these trade-offs between HDDs and SSDs in terms of cost, performance, and lifetime, the current consensus among several storage experts is to view SSDs not as a replacement for HDD but rather as a complementary device within the high performance storage hierarchy. We design and evaluate such a hybrid system called Hybrid Store to provide: (a) Hybrid Plan: improved capacity planning technique to administrators with the overall goal of operating within cost-budgets and (b) HybridDyn: improved performance/lifetime guarantees during episodes of deviations from expected workloads through two novel mechanisms: write-regulation and fragmentation busting. As an illustrative example of HybridStore's efficacy, Hybrid Plan is able to find the most cost-effective storage configuration for a large scale workload of Microsoft Research and suggest one MLC SSD with ten 7.2K RPM HDDs instead of fourteen 7.2K RPM HDDs only. HybridDyn is able to reduce the average response time for an enterprise scale random-write dominant workload by about 71%as compared to a HDD-based system.

Given a directed graph G = (V,E) and an integer k ≥ 1, a Steiner k-transitive-closure-spanner (Steiner k-TC-spanner) of G is a directed graph H = (VH, EH) such that (1) V ⊆ VH and (2) for all vertices v, u ∈ V, the distance from v to u in H is at most k if u is reachable from v in G, and ∞ otherwise. Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. We study the relationship between the dimension of a poset and the size, denoted Sk, of its sparsest Steiner k-TC-spanner. We present a nearly tight lower bound on S2 for d-dimensional directed hypergrids. Our bound is derived from an explicit dual solution to a linear programming relaxation of the 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a nearly tight lower bound on Sk for d-dimensional posets.

We develop constant-factor approximation algorithms for minimizing the maximum movement made by pebbles on a graph to reach a configuration in which the pebbles form a connected subgraph (connectivity), or interconnect a constant number of stationary nodes (Steiner tree). These problems model the minimization of the total time required to reconfigure a robot swarm to achieve a proximity (e.g., radio) network with these connectivity properties. Our approximation factors are tight up to constant factors, as none of these problems admit a (2 - e)-approximation assuming P ≠ NP.

We show that for some positive constant c it is not feasible to approximate Independent Set (for graphs of n vertices) within a factor of nc, provided Maximum 2-Satisfiability does not have a randomized polynomial time approximation scheme. We also study reductions preserving the quality of approximations and exhibit complete problems.

Given a connected graph G = (V ,E ) with nonnegative costs on edges, $c:E\rightarrow {\mathcal R}^+$, and a subset of terminal nodes R *** V , the Steiner tree problem asks for the minimum cost subgraph of G spanning R . The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.

We consider minimum equivalent digraph problem, its maximum optimization variant and some non-trivial extensions of these two types of problems motivated by biological and social network applications. We provide $\frac{3}{2}$-approximation algorithms for all the minimization problems and 2-approximation algorithms for all the maximization problems using appropriate primal-dual polytopes. We also show lower bounds on the integrality gap of the polytope to provide some intuition on the final limit of such approaches. Furthermore, we provide APX-hardness result for all those problems even if the length of all simple cycles is bounded by 5.

Motivated by the widespread proliferation of wireless networks employing directional antennas, we study some capacitated covering problems arising in these networks. Geometrically, the area covered by a directional antenna with parameters α,ρ,r is a set of points with polar coordinates (r,θ) such that r ≤ r and α ≤ θ ≤ α + ρ. Given a set of customers, their positions on the plane and their bandwidth demands, the capacitated covering problem considered here is to cover all the customers with the minimum number of directional antennas such that the demands of customers assigned to an antenna stays within a bound. We consider two settings of this capacitated cover problem arising in wireless networks. In the first setting where the antennas have variable angular range, we present an approximation algorithm with ratio 3. In the setting where the angular range of antennas is fixed, we improve this approximation ratio to 1.5.These results also apply for a related problem of bin packing with deadlines. In this problem we are are given a set of items, each with a weight, arrival time and deadline, and we want to pack each item into a bin after it arrives but before its deadline. The objective is to minimize the number of bins used. We present a 3-approximation algorithm for this problem, and 1.5-approximation algorithm for the special case when each difference between a deadline and the corresponding arrival time is the same.

Tovey [A simplified satisfiability problem, Discrete Appl. Math. 8 (1984) 85–89] showed that it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times, while every instance of 3-SAT in which each variable occurs three times is satisfiable. We explore the border between these two problems. Answering a question of Iwama and Takaki, we show that, for every fixed k⩾0, there is a polynomial-time algorithm to determine the satisfiability of 3-SAT instances in which k variables occur four times and the remaining variables occur three times. On the other hand, it is NP-hard to decide the satisfiability of 3-SAT instances in which all but one variable occurs three times, and the remaining variable is allowed to occur an arbitrary number of times.

Motivation: Complex genomes contain numerous repeated sequences, and genomic duplication is believed to be a main evolutionary mechanism to obtain new functions. Several tools are available for de novo repeat sequence identification, and many approaches exist for clustering homologous protein sequences. We present an efficient new approach to identify and cluster homologous DNA sequences with high accuracy at the level of whole genomes, excluding low-complexity repeats, tandem repeats and annotated interspersed repeats. We also determine the boundaries of each group member so that it closely represents a biological unit, e.g. a complete gene, or a partial gene coding a protein domain. Results: We developed a program called HomologMiner to identify homologous groups applicable to genome sequences that have been properly marked for low-complexity repeats and annotated interspersed repeats. We applied it to the whole genomes of human (hg17), macaque (rheMac2) and mouse (mm8). Groups obtained include gene families (e.g. olfactory receptor gene family, zinc finger families), unannotated interspersed repeats and additional homologous groups that resulted from recent segmental duplications. Our program incorporates several new methods: a new abstract definition of consistent duplicate units, a new criterion to remove moderately frequent tandem repeats, and new algorithmic techniques. We also provide preliminary analysis of the output on the three genomes mentioned above, and show several applications including identifying boundaries of tandem gene clusters and novel interspersed repeat families. Availability: All programs and datasets are downloadable from www.bx.psu.edu/miller_lab Contact: mhou@cse.psu.edu

The problems discussed here are motivated by a central concern of contemporary cell biology, that of unraveling (or “reverse engineering”) the web of interactions among the components of complex protein and genetic regulatory networks. Notwithstanding the remarkable progress in genetics and molecular biology in the sequencing of the genomes of a number of species, the inference and quantification of interconnections in signaling and genetic networks that are critical to cell function is still a challenging practical and theoretical problem. High-throughput technologies allow the monitoring the expression levels of sets of genes, and the activity states of signaling proteins, providing snapshots of the transcriptional and signaling behavior of living cells. Statistical and machine learning techniques, such as clustering, are often used in order to group genes ∗Supported by NSF grant CCR-0208821. †Supported in part by NSF grants CCR-0206795, CCR-0208749 and IIS-0346973. ‡Partly supported by NSF grants EIA 0205116 and DMS-0504557.

For a genomic region containing a tandem gene cluster, a proper set of alignments needs to align only orthologous segments, i.e., those separated by a speciation event. Otherwise, methods for finding regions under evolutionary selection will not perform properly. Conversely, the alignments should indicate every orthologous pair of genes or genomic segments. Attaining this goal in practice requires a technique for avoiding a combinatorial explosion in the number of local alignments. To better understand this process, we model it as a graph problem of finding a minimum cardinality set of cliques that contain all edges. We provide an upper bound for an important class of graphs (the problem is NP-hard and very difficult to approximate in the general case), and use the bound and computer simulations to evaluate two heuristic solutions. An implementation of one of them is evaluated on mammalian sequences from the α-globin gene cluster.

BackgroundIt has been proposed that secondary structure information can be used to classify (to some extend) protein folds. Since this method utilizes very limited information about the protein structure, it is not surprising that it has a higher error rate than the approaches that use full 3D fold description. On the other hand, the comparing of 3D protein structures is computing intensive. This raises the question to what extend the error rate can be decreased with each new source of information, especially if the new information can still be used with simple alignment algorithms.We consider the question whether the information about closed loops can improve the accuracy of this approach. While the answer appears to be obvious, we had to overcome two challenges. First, how to code and to compare topological information in such a way that local alignment of strings will properly identify similar structures. Second, how to properly measure the effect of new information in a large data sample.We investigate alternative ways of computing and presenting this information.ResultsWe used the set of beta proteins with at most 30% pairwise identity to test the approach; local alignment scores were used to build a tree of clusters which was evaluated using a new log-odd cluster scoring function. In particular, we derive a closed formula for the probability of obtaining a given score by chance.Parameters of local alignment function were optimized using a genetic algorithm.Of 81 folds that had more than one representative in our data set, log-odds scores registered significantly better clustering in 27 cases and significantly worse in 6 cases, and small differences in the remaining cases. Various notions of the significant change or average change were considered and tried, and the results were all pointing in the same direction.ConclusionWe found that, on average, properly presented information about the loop topology improves noticeably the accuracy of the method but the benefits vary between fold families as measured by log-odds cluster score.

In this paper, we consider the weighted online set k- multicover problem. In this problem, we have an universe V of elements, a family $\mathcal{S}$ of subsets of V with a positive real cost for every $S \in \mathcal{S}$, and a “coverage factor” (positive integer) k. A subset {i0, i1,...}⊆V of elements are presented online in an arbitrary order. When each element ip is presented, we are also told the collection of all (at least k) sets $\mathcal{S}_{i_p} \subseteq \mathcal{S}$ and their costs in which ip belongs and we need to select additional sets from $\mathcal{S}_{i_p}$ if necessary such that our collection of selected sets contains at leastk sets that contain the element ip. The goal is to minimize the total cost of the selected sets. In this paper, we describe a new randomized algorithm for the online multicover problem based on the randomized winnowing approach of [11]. This algorithm generalizes and improves some earlier results in [1]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [1].

In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished” by a family of “tests”, and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of “basic” tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem.

Given a strong match between regions of two sequences, how far can the match be meaningfully extended if gaps are allowed in the resulting alignment? The aim is to avoid searching beyond the point that a useful extension of the alignment is likely to be found. Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem. Given two sequences and a fixed X > 0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below −X. Our results indicate that computing an optimal alignment under this constraint is very expensive. However, less rigorous conditions on the alignment can be guaranteed by quite efficient algorithms. One of these variants has been implemented in a new release of the Blast suite of database search programs.

It is shown that in a standard discrete neural network model with small fan-in, tolerance to random malicious faults can be achieved with a log-linear increase in the number of neurons and a constant factor increase in parallel time, provided fan-in can increase arbitrarily. A similar result is obtained for a nonstandard but closely related model with no restriction on fan-in. >

In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows:•We abstract a combinatorial version of the problem and observe that this is “equivalent” to the set multicover problem when the “coverage” factor k is a function of the number of elements n of the universe. An important special case for our application is the case in which k=n-1.•We observe that the standard greedy algorithm produces an approximation ratio of Ω(logn) even if k is “large” i.e k=n-c for some constant c>0.•Let 1

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) with n/logn processors, if the elements are sorted.

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo [Fractal Merkle tree representation and traversal, in: RSA Cryptographers Track, RSA Security Conference, 2003] and M. Szydlo [Merkle tree traversal in log space and time, in: Proc. Eurocrypt, in: LNCS, vol. 3027, 2004, pp. 541-554; Merkle tree traversal in log space and time, Preprint version 2003, available at http://www.szydlo.com]. In particular, we show that our algorithm requires 2logn/log^(^3^)n hash function computations and storage for less than (logn/log^(^3^)n+1)loglogn+2logn hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than O(logn/logt) time and less than O(tlogn/logt) space for any choice of parameter t>=2. Our algorithm could be of special interest in the case when both time and space are limited.