This paper provides a deterministic online algorithm and a randomized online algorithm to search for suitable parameter values in Monte Carlo simulation for derivative pricing which are needed to achieve desired precisions. This paper also gives the competitive ratios of the two algorithms and proves the optimality of the algorithms. Experimental results on the performance of the algorithms are presented and analyzed as well.

This paper presents an efficient algorithm for finding the optimal k-cuts of a nondecreasing array of size n that produces the maximum area under the points. The naïve approach uses a dynamic programming algorithm which requires O(kn2) time, where n is the size of the array. This algorithm is time consuming for large n or k and thus inappropriate. We design faster algorithms by discovering and proving some nice properties of the nondecreasing arrays, finding convex hull, and by continuous-to-discrete transformation. We believe that an O(kn) time algorithm exists and show a heuristic algorithm.

Asian barrier options are barrier options whose trigger is based on an average underlying price. They provide the advantages of both Asian options and barrier options. This paper introduces the first quadratic-time lattice algorithm to price European-style Asian barrier options. It is by far the most efficient lattice algorithm with convergence guarantees. The algorithm relies on the Lagrange multipliers to optimally distribute the number of states for each node of the multinomial lattice. We also show experiment results to demonstrate effectiveness and efficiency of our algorithm by comparing with Monte Carlo simulations.

Financial derivative valuation is the key of the adoption of the International Financial Reporting Standards (IFRS), which are based on fair value accounting. When the derivatives do not have an active market, the inputs and methods for estimating their fair value will be more subjective and, the derivative valuation will be less reliable. The goal of this research is to design a derivative valuation service to aid the accounting professionals to meet the reliability requirement of the IFRS which, in the derivative setting, requires derivative valuation be objective and free from errors. First, we incorporate the various valuation models and their risk factors into the service as the basis for providing an objective valuation result. Second, we provide a user interface to simplified management of parameters and provisions of term sheets of derivatives to avoid users' errors in parsing the term sheets. Third, when the users hold a large number of derivatives, the derivative valuation meets real-time constraints in financial reporting. We thus developed the service in parallel computing environment to reduce computational time of the valuation process. Experiment cal results of derivative valuation are also presented.

This study considers all the possible actions a borrower may have, i.e., to default, to prepay, and to maintain the mortgage, during mortgage horizon. Then, we provide an effective and accurate pricing formula, which not only considers the effect that default might affect the mortgage value, but also more accurately explores the impact due to prepayment risk. In our model, we define prepayment value of the mortgage as the amount of outstanding principle. In contrast, previous literature defines prepayment value as a constant proportion of maintaining value of the mortgage. Finally, based on closed-form pricing formula, we analyze the yield, duration and convexity of risky mortgage loan, providing a better framework for risk management.

We study a natural probabilistic model for motif discovery. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet Σ. A motif G = g 1 g 2 … g m is a string of m characters. Each background sequence is implanted with a probabilistically generated approximate copy of G . For a probabilistically generated approximate copy b 1 b 2 … b m of G , every character is probabilistically generated such that the probability for b i ≠ g i is at most α. In this article, we develop an efficient algorithm that can discover a hidden motif from a set of sequences for any alphabet Σ with |Σ|≥ 2 and is applicable to DNA motif discovery. We prove that for α < 1/8(1- 1/|Σ|), there exist positive constants c 0 , ϵ, and δ 2 such that if there are at least c 0 log n input sequences, then in O ( n 2 / h (log n ) O (1)) time this algorithm finds the motif with probability at least 3/4 for every G ∈ Σ ρ -Ψ ρ, h ,ϵ (Σ), where n the length of longest sequences, ρ is the length of the motif, h is a parameter with ρ≥ 4 h ≥ δ 2 log n , and Ψ ρ, h ,ϵ (Σ) is a small subset of at most 2 −Θ(ϵ 2 h ) fraction of the sequences in Σ ρ .

In this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time.

We study a natural probabilistic model for motif discovery that has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet $\Sigma$. A motif $G=g_1g_2\cdots g_m$ is a string of m characters. Each background sequence is implanted into a probabilistically generated approximate copy of G. For an approximate copy $b_1b_2\cdots b_m$ of G, every character $b_i$ is probabilistically generated such that the probability for $b_i\neq g_i$ is at most $\alpha$. In this paper, we give the first analytical proof that multiple background sequences do help with finding subtle and faint motifs. This work is a theoretical approach with a rigorous probabilistic analysis. We develop an algorithm that under the probabilistic model can find the implanted motif with high probability when the number of background sequences is reasonably large. Specifically, we prove that for $\alpha<0.1771$ and any constant $x\geq8$, there exist constants $t_0,\delta_0,\delta_1>0$ such that if the length of the motif is at least $\delta_0\log n$, the alphabet has at least $t_0$ characters, and there are at least $\delta_1\log n_0$ input sequences, then in $O(n^3)$ time our algorithm finds the motif with probability at least $1-\frac{1}{2^x}$, where n is the longest length of any input sequence and $n_0\leq n$ is an upper bound for the length of the motif.

We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.

Nanoscale crossbars built from nanowires can form high density memories and programmable logic devices. To integrate such nanoscale devices with CMOS circuits, nanowire decoders were invented. Due to the stochastic nature of the nanoscale fabrication, the decoder addresses that address the nanowires selectively must be generated after fabrication. In this paper, we develop a mathematical model of the nanowire decoders for the generation of the proper addresses. Assuming a simple testing approach calledon-off measurement, we prove that the maximum number of the proper addresses can be generated in finite time. We design the algorithms to generate the required number of the proper addresses. Experimental results confirm the efficiency of our algorithms.

We consider the problem of detecting the presence of a sufficiently large number of hosts that connect to more than a certain number of unique destinations within a given time window, over high-speed networks. We call such hosts stealthy spreaders. In practice, stealthy spreaders can be symptomatic of botnet scans or moderate worm propagation. Previous techniques have focused on detecting sources with an extremely large outdegree. However, such techniques fail to detect spreaders such as bot scans in which each scanning host scans only a moderate, fixed number of destinations. In contrast, our scheme maintains a small, fixed size memory usage, and is still able to detect stealthy spreader scenarios by approximating outdegree histograms from continuous traffic. To the best of our knowledge, we are the first to study the efficient outdegree histogram estimation and stealthy spreader detection problems. Evaluation based on real Internet traffic and botnet scan events show that our scheme is highly accurate and can operate online.

A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to construct many aggregate queries. The recently proposed sketches (Krishnamurthy, 2003) are among the very few that can detect heavy changes online for high speed links, and thus support various aggregate queries in both temporal and spatial domains. However, it does not preserve the keys (e.g., source IP address) of flows, making it difficult to reconstruct the desired set of anomalous keys. In an earlier abstract we proposed a framework for a reversible sketch data structure that offers hope for efficient extraction of keys (Schweller, 2004). However, this scheme is only able to detect a single heavy change key and places restrictions on the statistical properties of the key space. To address these challenges, we propose an efficient reverse hashing scheme to infer the keys of culprit flows from reversible sketches. There are two phases. The first operates online, recording the packet stream in a compact representation with negligible extra memory and few extra memory accesses. Our prototype single FPGA board implementation can achieve a throughput of over 16 Gbps for 40-byte-packet streams (the worst case). The second phase identifies heavy changes and their keys from the representation in nearly real time. We evaluate our scheme using traces from large edge routers with OC-12 or higher links. Both the analytical and experimental results show that we are able to achieve online traffic monitoring and accurate change/intrusion detection over massive data streams on high speed links, all in a manner that scales to large key space size. To the best of our knowledge, our system is the first to achieve these properties simultaneously.

Zero-day polymorphic worms pose a serious threat to the security of Internet infrastructures. Given their rapid propagation, it is crucial to detect them at edge networks and automatically generate signatures in the early stages of infection. Most existing approaches for automatic signature generation need host information and are thus not applicable for deployment on high-speed network links. In this paper, we propose Hamsa, a network-based automated signature generation system for polymorphic worms which is fast, noise-tolerant and attack-resilient. Essentially, we propose a realistic model to analyze the invariant content of polymorphic worms which allows us to make analytical attack-resilience guarantees for the signature generation algorithm. Evaluation based on a range of polymorphic worms and polymorphic engines demonstrates that Hamsa significantly outperforms Polygraph (J. Newsome et al., 2005) in terms of efficiency, accuracy, and attack resilience

The family of Vickrey-Clarke-Groves (VCG) mechanisms is arguably the most celebrated achievement in truthful mechanism design. However, VCG mechanisms have their limitations. They only apply to optimization problems with a utilitarian (or affine) objective function, and their output should optimize the objective function. For many optimization problems, finding the optimal output is computationally intractable. If we apply VCG mechanisms to polynomial-time algorithms that approximate the optimal solution, the resulting mechanisms may no longer be truthful.In light of these limitations, it is useful to study whether we can design a truthful non-VCG payment scheme that is computationally tractable for a given allocation rule O. In this paper, we focus our attention on emphbinary demand games in which the agents' only available actions are to take part in the a game or not to. For these problems, we prove that a truthful mechanism M=(O, P) exists with a proper payment method P iff the allocation rule O satisfies a certain monotonicity property. We provide a general framework to design such P. We further propose several general composition-based techniques to compute P efficiently for various types of output. In particular, we show how P can be computed through "or/and" combinations, round-based combinations, and some more complex combinations of the outputs from subgames.

In this paper, we study the complexity of self-assembly under models that are natural generalizations of the tile self-assembly model. In particular, we extend Rothemund and Winfree's study of the tile complexity of tile self-assembly [Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 459--468]. They provided a lower bound of $\Omega(\frac{\log N}{\log\log N})$ on the tile complexity of assembling an $N\times N$ square for almost all N. Adleman et al. [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001, pp. 740--748] gave a construction which achieves this bound. We consider whether the tile complexity for self-assembly can be reduced through several natural generalizations of the model. One of our results is a tile set of size $O(\sqrt{\log N})$ which assembles an $N\times N$ square in a model which allows flexible glue strength between nonequal glues. This result is matched for almost all N by a lower bound dictated by Kolmogorov complexity. For three other generalizations, we show that the $\Omega(\frac{\log N}{\log\log N})$ lower bound applies to $N\times N$ squares. At the same time, we demonstrate that there are some other shapes for which these generalizations allow reduced tile sets. Specifically, for thin rectangles with length N and width k, we provide a tighter lower bound of $\Omega(\frac{N^{1/k}}{k})$ for the standard model, yet we also give a construction which achieves $O(\frac{\log N}{\log\log N})$ complexity in a model in which the temperature of the tile system is adjusted during assembly. We also investigate the problem of verifying whether a given tile system uniquely assembles into a given shape; we show that this problem is NP-hard for three of the generalized models.

A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the smallest number of edges to make a bipartite graph componentwise biconnected while preserving its bipartiteness. This algorithm has immediate applications for protecting sensitive information in statistical tables.

A universalization of a parameterized investment strategy is an online algorithm whose average daily performance approaches that of the strategy operating with the optimal parameters determined offline in hindsight. We present a general framework for universalizing investment strategies and discuss conditions under which investment strategies are universalizable. We present examples of common investment strategies that fit into our framework. The examples include both trading strategies that decide positions in individual stocks, and portfolio strategies that allocate wealth among multiple stocks. This work extends in a natural way Cover's universal portfolio work. We also discuss the runtime efficiency of universalization algorithms. While a straightforward implementation of our algorithms runs in time exponential in the number of parameters, we show that the efficient universal portfolio computation technique of Kalai and Vempala [Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000, pp. 486--491] involving the sampling of log-concave functions can be generalized to other classes of investment strategies, thus yielding provably good approximation algorithms in our framework.

Given a planar graph $\Ggg$ and a sequence ${\CC}_1,\ldots,{\CC}_q$, where each ${\CC}_i$ is a family of vertex subsets of $\Ggg$, we wish to find a plane embedding of $\Ggg$, if any exists, such that, for each $i\in\{1,\ldots,q\}$, there is a face F i in the embedding whose boundary contains at least one vertex from each set in CC i . This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let $\inputsize$ be the input size,i.e., the total number of vertices and edges in $\Ggg$ and the families CC i , counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in $O(\inputsize\log \inputsize)$ time for the special case in which, for each input family CC i , each set in CC i induces a connected subgraph of the input graph $\Ggg$. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints CC 1 , . . .,CC q incurs only a logarithmic factor of overhead.

In this paper we investigate the computational problem of predicting RNA secondary structures that allow any kinds of pseudoknots. The general belief is that allowing pseudoknots makes the problem very difficult. Existing polynomial-time algorithms, which aim at structures that optimize some energy functions, can only handle a certain types of pseudoknots. In this paper we initiate the study of approximation algorithms for handling all kinds of pseudoknots. We focus on predicting RNA secondary structures with a maximum number of stacking pairs and obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. Furthermore, we prove that allowing pseudoknots would make the problem of maximizing the number of stacking pairs on planar secondary structure to be NP-hard. This result should be contrasted with the recent NP-hard results on psuedoknots which are based on optimizing some peculiar energy functions.

paper presents the use of linear scaling and tree search in a content-based music retrieval system that can take a user's acoustic input (8-second clip of singing or humming) via a microphone and then retrieve the intended song from over 3000 candidate songs in the database. The system, known as Super MBox, demonstrates the feasibility of real-time content-based music retrieval with a high recognition rate. Super MBox first takes the user's acoustic input from a microphone and converts it into a pitch vector. Then a fast comparison engine using linear scaling and tree search is employed to compute the similarity scores. We have tested Super MBox and found the top-20 recognition rate is about 73% with about 1000 clips of test inputs from people with mediocre singing skills.

In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. We obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. We also compare this algorithm with the popular dollar averaging strategy using actual market data.

We give a greedy learning algorithm for reconstructing an evolutionary tree based on a certain harmonic average on triplets of terminal taxa. After the pairwise distances between terminal taxa are estimated from sequence data, the algorithm runs in $\smallbigO{\numtaxa^2}$ time using $\smallbigO{\numtaxa}$ work space, where $\numtaxa$ is the number of terminal taxa. These time and space complexities are optimal in the sense that the size of an input distance matrix is $\numtaxa^2$ and the size of an output tree is $\numtaxa$. Moreover, in the Jukes--Cantor model of evolution, the algorithm recovers the correct tree topology with high probability using sample sequences of length polynomial in (1) $\numtaxa$, (2) the logarithm of the error probability, and (3) the inverses of two small parameters.

Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k(x, y) be log x / log (x 2 /y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an $O(\sqrt{n}W / k(n, W/N))$-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G - {u} for all nodes u in O(W) time.

In this paper we study the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown. The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market. We show that for portfolios made up of two stocks, we can exactly and quickly solve the problem of finding an optimal portfolio for aggressive or risk-averse investors, using an algorithm based on a fast greedy solution to a maximum flow problem. However, an investor looking for an average-case guarantee (so is neither aggressive or risk-averse) must deal with a more difficult problem. In particular, we show that computing the distribution function associated with the average-case bound is ♯P-complete. On the positive side, we show how to use random sampling techniques similar to those for high-dimensional volume estimation to provide approximate answers. When k> 2 stocks are considered, we show that a simple solution based on the same flow concepts as our 2-stock algorithm would imply that P = NP, so is highly unlikely. We give approximation algorithms for this case as well as exact algorithms for some important special cases.

We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. To demonstrate the methodology, we discuss two nontrivial applications. The first is to decide whether a graph has a perfect matching in parallel. Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan. The second application is to test the equality of two multisets of integers. Our new algorithm improves upon the previously best algorithms by Blum and Kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property $\pi$ is called a {\em $\pi$-graph}. If $\pi$ satisfies certain properties, then an n-node m-edge $\pi$-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most $\beta(n)+o(\beta(n))$ bits for any continuous superadditive function $\beta(n)$ so that there are at most $2^{\beta(n)+o(\beta(n))}$ distinct n-node $\pi$-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such $\pi$ include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from $\{1,\ldots, \ell_1\}$ for $\ell_1\leq n$; (5) the edges of G are labeled with labels from $\{1,\ldots, \ell_2\}$ for $\ell_2\leq m$; and (6) each node (respectively, edge) of G has at most $\ell_3=O(1)$ self-loops (respectively, $\ell_4=O(1)$ multiple edges). Moreover, $\ell_3$ and $\ell_4$ are not required to be O(1) for the cases of $\pi$ being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.

We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n 1.5 log n) time for trees with unbounded degrees, matching the best known time complexity for the rooted case. Our algorithm allows the input trees to be mixed trees, i.e., trees that may contain directed and undirected edges at the same time. Our algorithm adopts a recursive strategy exploiting a technique called label compression. The backbone of this technique is an algorithm that computes the maximum weight matchings over many subgraphs of a bipartite graph as fast as it takes to compute a single matching.

Given a multiset X={x 1 ,. . .,x n } of real numbers, the floating-point set summation problem asks for S n =x 1 + . . . + x n . Let $E^*_n$ denote the minimum worst-case error over all possible orderings of evaluating S n . We prove that if X has both positive and negative numbers, it is NP-hard to compute S n with the worst-case error equal to $E^*_n$. We then give the first known polynomial-time approximation algorithm that has a provably small error for arbitrary X. Our algorithm incurs a worst-case error at most $2(\lceil\log(n-1)\rceil+1)E^*_n$. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(n) time. For the case where X is either all positive or all negative, we give another approximation algorithm with a worst-case error at most $\lceil\log\log n\rceil E^*_n$. Even for unsorted X, this algorithm runs in O(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most $\lceil\log n\rceil E^*_n$, while $E^*_n$ was known to be attainable in O(n log n) time using Huffman coding.

In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. We obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. We also compare this algorithm with the popular dollar averaging strategy using actual market data.

This paper studies some basic problems in a multiple-object auction model using methodologies from theoretical computer science. We are especially concerned with situations where an adversary bidder knows the bidding algorithms of all the other bidders. In the two-bidder case, we derive an optimal randomized bidding algorithm, by which the disadvantaged bidder can procure at least half of the auction objects despite the adversary's a priori knowledge of his algorithm. In the general k-bidder case, if the number of objects is a multiple of k, an optimal randomized bidding algorithm is found. If the k -- 1 disadvantaged bidders employ that same algorithm, each of them can obtain at least 1/k of the objects regardless of the bidding algorithm the adversary uses. These two algorithms are based on closed-form solutions to certain multivariate probability distributions. In situations where a closed-form solution cannot be obtained, we study a restricted class of bidding algorithms as an approximation to desired optimal algorithms.

Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using 4/3m-1 bits, improving on the best previous bound of about 1.53m bits. In case exponential time is acceptable, roughly 1.08m bits have been known to suffice. If G is triconnected, we use at most $(2.5+2\log{3})\min\{n,f\}-7$ bits, which is at most 2.835m bits and smaller than the best previous bound of 3m bits. Both of our schemes take O(n) time for encoding and decoding.

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n-O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small---at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is $n^2/8-\Theta(n\log n)$. An analysis shows that the optimal expected off-line gain is $n^2/6+\Theta(1)$, so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.

This paper studies how to concurrently permute related logical or physical submeshes in a d-dimensional n× … × n physical mesh via wormhole and dimension-ordered routing. Our objective is to minimize the congestion for realizing the permutations, while maximizing the number and dimensionality of permuted submeshes. We show that for d ⩽ 2α + β, concurrent independent permutations of nβ related physical submeshes, each of α dimensions, can be performed in two routing steps without congestion. If the permuted submeshes are logical ones, they can be permuted in one, instead of two, routing step. In addition, any shift operation along any axis of the logical mesh can be performed in the physical mesh without congestion. We also show that if all nodes know the permutation function, any permutation within a submesh of dimensions ⌊2(d − 1)/3⌋ can be realized in three routing steps without congestion.

An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T 1 and T 2 with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log 2 n) and is within a log n factor of optimal. For general d, this algorithm runs in O(nd 2 log d log 2 n) time or alternatively in $O(ndsqrt{d}\log^3{n})$ time.

Studies statistical database problems for 2D tables whose regular cells, row sums, column sums and table sums may be suppressed. Using graph-theoretical techniques, we give optimal or efficient algorithms for the query system problem, the adversary problem and the minimum complementary suppression problem. These three problems are considered for a variety of data security requirements such as those of protecting linear invariants, analytic invariants, k rows (or columns) as a whole, and a table as a whole.

. We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. To demonstrate the methodology, we discuss two nontrivial applications. The first is to decide whether a graph has a perfect matching in parallel. Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan. The second application is to test the equality of two multisets of integers. Our new algorithm improves upon the previously best algorithms ...

This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dvnamic programming.The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agree ment subtrees into new ones for unrooted trees.Let n be the size of the two input trees.This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case.The technique of label compression is not based on dynamic programming.With this technique, we obtain an O(nl"5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

To protect sensitive information in a cross-tabulated table, it is a common practice to suppress some of the cells in the table. An analytic invariant is a power series in terms of the suppressed cells that has a unique feasible value and a convergence radius equal to $+\infty$. Intuitively, the information contained in an invariant is not protected even though the values of the suppressed cells are not disclosed. This paper gives an optimal linear-time algorithm for testing whether there exist nontrivial analytic invariants in terms of the suppressed cells in a given set of suppressed cells. This paper also presents NP-completeness results and an almost linear-time algorithm for the problem of suppressing the minimum number of cells in addition to the sensitive ones so that the resulting table does not leak analytic-invariant information about a given set of suppressed cells.

To protect sensitive information in a cross-tabulated table, it is a common practice to suppress some of the cells in the table. This paper investigates four levels of data security of a two-dimensional table concerning the effectiveness of this practice. These four levels of data security protect the information contained in, respectively, individual cells, individual rows and columns, several rows or columns as a whole, and a table as a whole. The paper presents efficient algorithms and NP-completeness results for testing and achieving these four levels of data security. All these complexity results are obtained by means of fundamental equivalences between the four levels of data security of a table and four types of connectivity of a graph constructed from that table.

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L/sub /spl infin// norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than the offline optimal. In many applications, the L/sub /spl infin// norm is not a suitable way to measure how well the jobs are balanced, If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

This paper proves that for a strongly connected planar directed graph of size n, a depth-first search tree rooted at a specified vertex can be computed in $O(\log^{5} n)$ time with $n/ \log n$ processors. Previously, for planar directed graphs that may not be strongly connected, the best depth-first search algorithm runs in $O(\log^{10} n)$ time with n processors. Both algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory, and in case of a write conflict, permits an arbitrary processor to succeed.

We give an optimal algorithm that broadcasts on an n-dimensional hypercube in O(n/ log/sub 2/ (n+1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of P.K. McKinley and C. Trefftz (1993) requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n /spl les/7.>

Presents advanced data compression techniques for predicting stock markets behavior under widely accepted market models in finance. The techniques are applicable to technical analysis, portfolio theory, and nonlinear market models. The authors find that lossy and lossless compression techniques are well suited for predicting stock prices as well as market modes such as strong trends and major adjustments. They also present novel applications of multispectral compression techniques to portfolio theory, correlation of similar stocks, effects of interest rates, transaction costs and taxes.>

We give an optimal algorithm that broadcasts on an n-dimensional hypercube in Theta(n/ log_{2}(n+ 1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of McKinley and Trefftz requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n leqslant 7.

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with $n \geq 3$, a straight-line embedding on a grid of size $( n - 2 ) \times ( n - 2 )$ can be computed deterministically in $O( \log n\log \log n )$ time with $n/\log n\log \log n$ processors. If randomization is used, the complexity is improved to $O( \log n )$ expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.

We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific communication configuration, but its running time is not known until it is completed. We present optimal online algorithms for PRAMs, hypercubes and one-dimensional meshes, and obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested...

Given a graph $G = (V,E)$, a certificate of k-vertex connectivity is an edge subset $E' \subset E$ such that the subgraph $(V,E')$ is k-vertex connected if and only if G is k-vertex connected. Let n and m denote the number of vertices and edges. A certificate is called sparse if it contains $O(kn)$ edges. For undirected graphs, this paper introduces a graph search called the scan-first search, and shows that a certificate with at most $k(n - 1)$ edges can be computed by executing scan-first search k times in sequence on subgraphs of G. For each of the parallel, distributed, and sequential models of computation, the complexity of scan-first search matches the best complexity of any graph search on that model. In particular, the parallel scan-first search runs in $O(\log n)$ time using $C(n,m)$ processors on a CRCW PRAM, where $C(n,m)$ is the number of processors needed to find a spanning tree in each connected component in $O(\log n)$ time, and the parallel certificate algorithm runs in $O(k\log n)$ time using $C(n,m)$ processors. The parallel certificate algorithm can be employed to test the k-vertex connectivity of an undirected graph in $O(k^2 \log n)$ time using $knC(n,kn)$ processors on a CRCW PRAM. For all combinations of n, m, and $k > 3$, both the running time and the number of processors either improve on or match those of all known deterministic parallel algorithms. This paper also obtains an online algorithm for computing an undirected graph certificate with at most $2kn$ edges, and a sequential algorithm for computing a directed graph certificate with at most $2k^2 n$ edges.

Finding strongly connected components is a fundamental step in many algorithms for directed graphs. In sequential computation this problem has an optimal linear-time algorithm. In parallel computation, however, it remains an open problem whether polylogarithmic time and a linear number of processors are sufficient for computing the strongly connected components on a parallel random-access machine. This paper provides the first nontrivial partial solution to the open problem: for a planar directed graph of size n the strongly connected components can be computed deterministically in $O(\log ^3 n)$ time with ${n / {\log n}}$ processors. The algorithm runs on a parallel random-access machine that allows concurrent reads and concurrent writes in its shared memory and, in case of a write conflict, permits an arbitrary processor to succeed.

It is a fundamental open problem whether polylogarithmic time and a linear number of processors are sufficient for computing the strongly connected components of a directed graph and constructing directed spanning trees for these components. This paper provides the first nontrivial partial solution to the tree problem: for a strongly connected planar directed graph of size n a directed spanning tree rooted at a specified vertex can be computed in $O(\log ^2 n)$ time with ${n / {\log n}}$ processors. This result complements an algorithm by Kao that computes the strongly connected components of a planar directed graph in $O(\log ^3 n)$ time with ${n / {\log n}}$ processors. Both algorithms run on a deterministic parallel random-access machine that permits concurrent reads and concurrent writes in its shared memory and, in case of a write conflict, allows an arbitrary processor to succeed.

To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. A linear combination of suppressed cells is called a linear invariant if the combination has a unique feasible value. Intuitively, the information contained in an invariant is not protected even though the values of the suppressed cells are not disclosed. This paper gives a surprisingly efficient algorithm for testing whether a linear combination of suppressed cells is an invariant. In sequential computation, the algorithm runs in optimal linear time. In parallel computation, the algorithm runs in polylogarithmic time using a polynomial number of processors on a parallel random access machine. The algorithm exploits a linear algebraic structure of directed and undirected cycles in a mixed graph induced by a given table. This new structure also plays a crucial role in subsequent papers on other aspects of detecting and protecting sensitive information in a cross tabulated table.

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight lines joining their incident vertices.Given an n-vertex planar graph with n ~3, a straight-line embedding on a grid of size (n-2)X(n-2) can be computed deterministically in O(log n log log n) time with O(n log log n) work on a parallel random access machine.If randomization is used, the complexity is improved to O(log n) expected time with the same work bound.The parallel random access machine used by these algorithms allows concurrent reads and concurrent writes of the shared memory; in case of a write conflict, an arbitrary processor succeeds.sonably small grids are very useful in visualizing planar graphs on graphic screens and have wide applications in CAD/CAM and Computer Graphics [8], [27].Wagner [28], Fziry [9], and Stein [24] showed that every planar graph has a straight-line embedding.Since

Currently, there is a significant gap between the best sequential and parallel complexities of many fundamental problems related to digraph reachability.This complexity bottleneck essentially reflects a seemingly unavoidable reliance on transitive closure techniques in parallel algorithms for digraph reachability.To pinpoint the nature of the bottleneck, we de* velop a collection of polylog-time reductions among reachability problems.These reductions use only linear processors and work for general graphs.Furthermore, for planar digraphs, we give polylog-time algorithms for the following problems: (1) directed ear decomposition, (2) topological ordering, (3) digraph reachability, (4) descendent counting, and (5) depth-first search.These algorithms use only linear processors and therefore reduce the complexity to within a polylog factor of optimal.

A directed cycle separator of an n-vertex directed graph is a vertex-simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than ${n / 2}$ vertices. It is shown that the problem of finding a directed cycle separator is in randomized NC. It is also proved that computing cycle separators and conducting depth-first search in directed graphs are deterministically NC-equivalent. These two results together yield the first randomized NC algorithm for depth-first search in general directed graphs.

A directed cycle separator of an n-vertex directed graph is a simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than n/2 vertices. This paper shows that the problem of finding a directed cycle separator is in randomized NC. The paper also proves that computing cycle separators and conducting depth-first search in directed graphs are deterministic NC-equivalent. These two results together yield the first RNC algorithm for depth-first search in directed graphs.

Almost every problem on digraphs requires computing strongly connected components and directed spanning trees in one form or another. It has long been an open problem whether polylog time and linear processors are enough to find the strongly connected components of a digraph and compute directed spanning trees for these components. This paper provides the first non-trivial partial solution to this open problem: For a planar digraph with n vertices, the strongly connected components can be computed in O(log3n) time and O(n) processors. If the graph is strongly connected, a directed spanning tree can be built in O(log2 n) time and O(n) processors. Both algorithms are deterministic and run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory.