The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model.

We study the problem of learning a most biased coin among a set of coins by tossing the coins adaptively. The goal is to minimize the number of tosses until we identify a coin whose posterior probability of being most biased is at least 1-δfor a given δ. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy—a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any given starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs mathematical tools from the area of Markov games.

Detecting essential multiprotein modules that change infrequently during evolution is a challenging algorithmic task that is important for understanding the structure, function, and evolution of the biological cell. In this paper, we define a measure of modularity for interactomes and present a linear-time algorithm, Produles, for detecting multiprotein modularity conserved during evolution that improves on the running time of previous algorithms for related problems and offers desirable theoretical guarantees. We present a biologically motivated graph theoretic set of evaluation measures complementary to previous evaluation measures, demonstrate that Produles exhibits good performance by all measures, and describe certain recurrent anomalies in the performance of previous algorithms that are not detected by previous measures. Consideration of the newly defined measures and algorithm performance on these measures leads to useful insights on the nature of interactomics data and the goals of previous and current algorithms. Through randomization experiments, we demonstrate that conserved modularity is a defining characteristic of interactomes. Computational experiments on current experimentally derived interactomes for Homo sapiens and Drosophila melanogaster, combining results across algorithms, show that nearly 10 percent of current interactome proteins participate in multiprotein modules with good evidence in the protein interaction data of being conserved between human and Drosophila.

A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n–(1/p) log np(1 − o(1)) with probability at least 3/4 for the random graph Gn,p (the smallest feedback vertex set is of size n − (2/p) log np(1 + o(1))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted random graph and this allows us to exactly recover the planted feedback vertex set.

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width-w poset of size n with query complexity $O(n(w+\log n))$ and prove that this query complexity is asymptotically optimal. We also describe a variant of Mergesort with query complexity $O(wn\log\frac{n}{w})$ and total complexity $O(w^{2}n\log\frac{n}{w})$; an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k “levels,” called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with query complexity and total complexity $O(wn)$. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

In the network querying problem, one is given a protein complex or pathway of species A and a protein-protein interaction network of species B; the goal is to identify subnetworks of B that are similar to the query in terms of sequence, topology, or both. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species A; however, in practice, this topology is often not known. To address this problem, we develop a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test Torque with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than QNet, while giving results that are highly functionally coherent.

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n(w + log n)). We also describe a variant of Mergesort with query complexity and total complexity ; an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k “levels”, called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(wn) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

Summary form only given. This article trace the growing influence of fundamental ideas from computer science on the nature of research in a number of scientific fields. There is a growing awareness that information processing lies at the heart of the processes studied in fields as diverse as quantum mechanics, statistical physics, nanotechnology, neuroscience, linguistics, economics and sociology. Increasingly, mathematical models in these fields are expressed in algorithmic languages and describe algorithmic processes. The author describe connections between quantum computing and the foundations of quantum mechanics, and between statistical mechanics and phase transitions in computation. The author indicates how the growth of the Web has created new phenomena to be investigated by sociologists and economists, spurring new developments in computational game theory and the study of social networks. The author then focus on computational molecular biology, where the view of living cells as complex information processing systems has become the dominant paradigm.

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous nonasymptotic results for LDPC codes, and in particular, exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a flow on the Tanner graph of the code. An interesting by-product of our analysis is to establish the existence of ldquoprobabilistic expansionrdquo in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst case setting.

This talk will trace the growing influence of fundamental ideas from computer science on the nature of research in a number of scientific fields. There is a growing awareness that information processing lies at the heart of the processes studied in fields as diverse as quantum mechanics, statistical physics, nanotechnology, neuroscience, linguistics, economics and sociology. Increasingly, mathematical models in these fields are expressed in algorithmic languages and describe algorithmic processes. The speaker will briefly describe connections between quantum computing and the foundations of quantum mechanics, and between statistical mechanics and phase transitions in computation. He will indicate how the growth of the Web has created new phenomena to be investigated by sociologists and economists. He will then focus in greater detail on computational molecular biology, where the view of living cells as complex information processing systems has become the dominant paradigm, and will discuss specific algorithmic problems arising in the sequencing of genomes, the comparative analysis of the resulting genomic sequences, the modeling of networks of interacting proteins, and the associations between genetic variation and disease.

We address the problem of balancing the traffic load in multi-hop wireless networks. We consider a point-to-point communicating network with a uniform distribution of source-sink pairs. When routing along shortest paths, the nodes that are centrally located forward a disproportionate amount of traffic. This translates into increased congestion and energy consumption. However, the maximum load can be decreased if the packets follow curved paths. We show that the optimum such routing scheme can be expressed in terms of geometric optics and computed by linear programming. We then propose a practical solution, which we call Curveball Routing that achieves results not much worse than the optimum. We evaluate our solution at three levels of fidelity: a Java high-level simulator, the ns2 simulator, and the Intel Mirage Sensor Network Testbed. Simulation results using the high-level simulator show that our solution successfully avoids the crowded center of the network, and reduces the maximum load by up to 40%. At the same time, the increase of the expected path length is small, i.e., only 8 % on average. Simulation results using the ns2 simulator show that our solution can increase throughput on moderately loaded networks by up to 15%, while testbed results show a reduction in peak message load by up to 25%. Our prototype suggests that our solution is easily deployable.

This talk will trace the growing influence of fundamental ideas from computer science on the nature of research in a number of scientific fields. There is a growing awareness that information processing lies at the heart of the processes studied in fields as diverse as quantum mechanics, statistical physics, nanotechnology, neuroscience, linguistics, economics and sociology. Increasingly, mathematical models in these fields are expressed in algorithmic languages and describe algorithmic processes. The speaker will briefly describe connections between quantum computing and the foundations of quantum mechanics, and between statistical mechanics and phase transitions in computation. He will indicate how the growth of the Web has created new phenomena to be investigated by sociologists and economists. He will then focus in greater detail on computational molecular biology, where the view of living cells as complex information processing systems has become the dominant paradigm, and will discuss specific algorithmic problems arising in the sequencing of genomes, the comparative analysis of the resulting genomic sequences,the modeling of networks of interacting proteins, and the associations between genetic variation and disease.

MOTIVATION: The search for genetic variants that are linked to complex diseases such as cancer, Parkinson's;, or Alzheimer's; disease, may lead to better treatments. Since haplotypes can serve as proxies for hidden variants, one method of finding the linked variants is to look for case-control associations between the haplotypes and disease. Finding these associations requires a high-quality estimation of the haplotype frequencies in the population. To this end, we present, HaploPool, a method of estimating haplotype frequencies from blocks of consecutive SNPs. RESULTS: HaploPool leverages the efficiency of DNA pools and estimates the population haplotype frequencies from pools of disjoint sets, each containing two or three unrelated individuals. We study the trade-off between pooling efficiency and accuracy of haplotype frequency estimates. For a fixed genotyping budget, HaploPool performs favorably on pools of two individuals as compared with a state-of-the-art non-pooled phasing method, PHASE. Of independent interest, HaploPool can be used to phase non-pooled genotype data with an accuracy approaching that of PHASE. We compared our algorithm to three programs that estimate haplotype frequencies from pooled data. HaploPool is an order of magnitude more efficient (at least six times faster), and considerably more accurate than previous methods. In contrast to previous methods, HaploPool performs well with missing data, genotyping errors and long haplotype blocks (of between 5 and 25 SNPs).

Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system's performance as a function of its nodes' capacities C and workload W (such as the completion time of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity α when for any workload, cost cannot increase by more than a factor α if node capacities become arbitrarily more heterogeneous. We give constant bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that increasing heterogeneity can never be much of a disadvantage. On the other hand, with the introduction of timing constraints such as release times or precedence constraints on the jobs, the dependence on node capacities becomes more complex, so that increasing heterogeneity may be quite detrimental.

The following problems arise in the analysis of biological networks: We have a boolean function of n variables, each of which has some default value. An experiment fixes the values of any subset of the variables, the remaining variables assume their default values, and the function value is the result of the experiment. How many experiments are needed to determine (reconstruct) the function? How many experiments that involve fixing at most q values are needed? What are the answers to these questions when an unknown subset of the variables are actually involved in the function? In the biological context, the variables are genes and the values are gene expression intensities. An experiment measures the gene levels under conditions that perturb the values of a subset of the genes. The goal is to reconstruct the particular logic (regulation function) by which a subset of the genes together regulate one target gene, using few experiments that involve minor perturbations. We study these questions under the assumption that all functions belong to a biologically motivated set of so‐called chain functions. We give optimal reconstruction schemes for several scenarios and show their application in reconstructing the regulation of galactose utilization in yeast.

In this paper we extend the double verification algorithm of Luby and Mitzenmacher to the class of Raptor codes, analyze it, and design Raptor codes that perform very well with respect to this algorithm

Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having /spl theta/(log N) times as many objects as the average node. Further imbalance may result due to non-uniform distribution of objects in the identifier space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can be expected to experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes. We propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm achieves load balancing for system utilizations as high as 90% while moving only about 8% of the load that arrives into the system. Similarly, in a dynamic system where nodes arrive and depart, our algorithm moves less than 60% of the load the underlying DHT moves due to node arrivals and departures. Finally, we show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm.

This paper provides an efficient method for analyzing the error probability of the belief propagation (BP) decoder applied to LT Codes. Each output symbol is generated independently by sampling from a distribution and adding the input symbols corresponding to the support of the sampled vector.

This paper is concerned with the reconstruction of perfect phylogenies from binary character data with missing values, and related problems of inferring complete haplotypes from haplotypes or genotypes with missing data. In cases where the problems considered are NP-hard we assume a rich data hypothesis under which they become tractable. Natural probabilistic models are introduced for the generation of character vectors, haplotypes or genotypes with missing data, and it is shown that these models support the rich data hypothesis. The principal results include: • A near-linear time algorithm for inferring a perfect phylogeny from binary character data (or haplotype data) with missing values, under the rich data hypothesis; • A quadratic-time algorithm for inferring a perfect phylogeny from genotype data with missing values with high probability, under certain distributional assumptions; • Demonstration that the problems of maximum-likelihood inference of complete haplotypes from partial haplotypes or partial genotypes can be cast as minimum-entropy disjoint set cover problems; • In the case where the haplotypes come from a perfect phylogeny, a representation of the set cover problem as minimum-entropy covering of subtrees of a tree by nodes;

A major focus of functional genomics today is the discovery of the interactions between genes and proteins that regulate the transcription of genes and the responses of cells to external signals. The speaker will describe his recent efforts with several coworkers to solve pieces of this puzzle. The work divides into several parts:

Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to yeast S. Cerevisiae and bacteria H. pylori. Our analysis combines protein interaction data, that are available for each of the two species, and orthology information based on protein sequence comparison. We develop a detailed probabilistic model for protein complexes in a single species, and a model for the conservation of complexes between two species. Using these models, one can recast the question of finding conserved complexes as a problem of searching for heavy subgraphs in an edge- and node-weighted graph, whose nodes are orthologous protein pairs.We tested this approach on the data currently available for yeast and bacteria and detected 11 significantly conserved complexes. Several of these complexes match very well with prior experimental knowledge on complexes in yeast only, and serve for validation of our methodology. The complexes suggest new functions for a variety of uncharacterized proteins. By identifying a conserved complex whose yeast proteins function predominantly in the nuclear pore complex, we propose that the corresponding bacterial proteins function as a coherent cellular membrane transport system. We also compare our results to two alternative methods for detecting complexes, and demonstrate that our methodology obtains a much higher specificity.

Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which are mutations at a single nucleotide position. To characterize an individual's variation, we must determine an individual's haplotype or which nucleotide base occurs at each position of these common SNPs for each chromosome. In this paper, we present results for a highly accurate method for haplotype resolution from genotype data. Our method leverages a new insight into the underlying structure of haplotypes which shows that SNPs are organized in highly correlated "blocks". The majority of individuals have one of about four common haplotypes in each block. Our method partitions the SNPs into blocks and for each block, we predict the common haplotypes and each individual's haplotype. We evaluate our method over biological data. Our method predicts the common haplotypes perfectly and has a very low error rate (0.47%) when taking into account the predictions for the uncommon haplotypes. Our method is extremely efficient compared to previous methods, (a matter of seconds where previous methods needed hours). Its efficiency allows us to find the block partition of the haplotypes, to cope with missing data and to work with large data sets such as genotypes for thousands of SNPs for hundreds of individuals. The algorithm is available via webserver at http://www.cs.columbia.edu/compbio/hap.

Consider the following stochastic process executed on a graph G=(V,E) whose nodes are initially uncovered. In each step, pick a node at random and if it is uncovered, cover it. Otherwise, if it has an uncovered neighbor, cover a random uncovered neighbor. Else, do nothing. This can be viewed as a structured coupon collector process. We show that for a large family of graphs, O(n) steps suffice to cover all nodes of the graph with high probability, where n is the number of vertices. Among these graphs are d-regular graphs with d =Ω(log n log log n), random d-regular graphs with d =Ω(log n) and the k-dimensional hypercube where n=2k.This process arises naturally in answering a question on load balancing in peer-to-peer networks. We consider a distributed hash table in which keys are partitioned across a set of processors, and we assume that the number of processors grows dynamically, starting with a single processor. If at some stage there are n processors, the number of queries required to find a key is log2 n+O(1), the number of pointers maintained by each processor is log2 n+O(1), and moreover the worst ratio between the loads of processors is O(1), with high probability. To the best of our knowledge, this is the first analysis of a distributed hash table that achieves asymptotically optimal load balance, while still requiring only O(log n) pointers per processor and O(log n) queries for locating a key; previous methods required Ω(log2 n) pointers per processor and Ω(log n) queries for locating a key.

We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is an on-line algorithm, generalizing a well-known algorithm for finding a majority element, for identifying a set of at most 1/θ items that includes, possibly among others, all items with frequency greater than θ.

A number of large-scale distributed Internet applications could potentially benefit from some level of knowledge about the relative proximity between its participating host nodes. For example, the performance of large overlay networks could be improved if the application-level connectivity between the nodes in these networks is congruent with the underlying IP-level topology. Similarly, in the case of replicated Web content, client nodes could use topological information in selecting one of multiple available servers. For such applications, one need not find the optimal solution in order to achieve significant practical benefits. Thus, these applications, and presumably others like them, do not require exact topological information and can instead use sufficiently informative hints about the relative positions of Internet hosts. In this paper, we present a binning scheme whereby nodes partition themselves into bins such that nodes that fall within a given bin are relatively close to one another in terms of network latency. Our binning strategy is simple (requiring minimal support from any measurement infrastructure), scalable (requiring no form of global knowledge, each node only needs knowledge of a small number of well-known landmark nodes) and completely distributed (requiring no communication or cooperation between the nodes being binned). We apply this binning strategy to the two applications mentioned above: overlay network construction and server selection. We test our binning strategy and its application using simulation and Internet measurement traces. Our results indicate that the performance of these applications can be significantly improved by even the rather coarse-grained knowledge of topology offered by our binning scheme.

We propose a dynamic Bayesian model for motifs in biopolymer se- quences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model posits that the position-specific multinomial parameters for monomer distribu- tion are distributed as a latent Dirichlet-mixture random variable, and the position-specific Dirichlet component is determined by a hidden Markov process. Model parameters can be fit on training motifs using a vari- ational EM algorithm within an empirical Bayesian framework. Varia- tional inference is also used for detecting hidden motifs. Our model im- proves over previous models that ignore biological priors and positional dependence. It has much higher sensitivity to motifs during detection and a notable ability to distinguish genuine motifs from false recurring patterns.

This paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. Most existing methods for pattern discovery in such matrices are based on clustering genes by comparing their expression levels in all experiments, or clustering experiments by comparing their expression levels for all genes. Our work goes beyond such global approaches by looking for local patterns that manifest themselves when we focus simultaneously on a subset G of the genes and a subset T of the experiments. Specifically, we look for order-preserving submatrices (OPSMs), in which the expression levels of all genes induce the same linear ordering of the experiments (we show that the OPSM search problem is NP-hard in the worst case). Such a pattern might arise, for example, if the experiments in T represent distinct stages in the progress of a disease or in a cellular process, and the expression levels of all genes in G vary across the stages in the same way.We define a probabilistic model in which an OPSM is hidden within an otherwise random matrix. Guided by this model we develop an efficient algorithm for finding the hidden OPSM in the random matrix. In data generated according to the model the algorithm recovers the hidden OPSM with very high success rate. Application of the methods to breast cancer data seems to reveal significant local patterns.Our algorithm can be used to discover more than one OPSM within the same data set, even when these OPSMs overlap. It can also be adapted to handle relaxations and extensions of the OPSM condition. For example, we may allow the different rows of G x T to induce similar but not identical orderings of the columns, or we may allow the set T to include more than one representative of each stage of a biological process.

Most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation and relative distance is unknown. We propose here a new technique that supplements the shotgun assembly data by cheap and simple complete restriction digests of the target. By computationally combining information from the contig sequences and the fragment sizes measured for several different enzymes, we seek to form a "scaffold" on which the contigs will be placed in their correct orientation, order and distance. We give a heuristic search algorithm for solving the problem and report on promising preliminary simulation results. The key to the success of the search scheme is the very rapid solution of its two time-critical subproblems that are solved precisely in linear time.Our simulations indicate that with noise levels of some 3% relative error in measuring fragment sizes, using five enzymes, most datasets of 20 contigs can be correctly ordered, and the remaining ones have most of their pairs of neighboring contigs correct. Hence, the technique has a potential to provide real help to finishing. Even when the target clone remains unfinished, the ability to order and orient the contigs correctly makes the partial assembly both more accessible and more useful for biologists.

For years, the conventional wisdom [7, 22] has been that the continued stability of the Internet depends on the widespread deployment of "socially responsible" congestion control. In this paper, we seek to answer the following fundamental question: If network end-points behaved in a selfish manner, would the stability of the Internet be endangered?.We evaluate the impact of greedy end-point behavior through a game-theoretic analysis of TCP. In this "TCP Game" each flowattempts to maximize the throughput it achieves by modifying its congestion control behavior. We use a combination of analysis and simulation to determine the Nash Equilibrium of this game. Our question then reduces to whether the network operates efficiently at these Nash equilibria.Our findings are twofold. First, in more traditional environments -- where end-points use TCP Reno-style loss recovery and routers use drop-tail queues -- the Nash Equilibria are reasonably efficient. However, when endpoints use more recent variations of TCP (e.g., SACK) and routers employ either RED or drop-tail queues, the Nash equilibria are very inefficient. This suggests that the Internet of the past could remain stable in the face of greedy end-user behavior, but the Internet of today is vulnerable to such behavior. Second, we find that restoring the efficiency of the Nash equilibria in these settings does not require heavy-weight packet scheduling techniques (e.g., Fair Queuing) but instead can be done with a very simple stateless mechanism based on CHOKe [21].

We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisfiable. First, building on the work of Clegg, Edmonds, and Impagliazzo in [Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, 1996, ACM, New York, 1996, pp. 174--183], we give an algorithm for unsatisfiability that when given an unsatisfiable formula of F finds a resolution proof of F. The runtime of our algorithm is subexponential in the size of the shortest resolution proof of F. Next, we investigate a class of backtrack search algorithms for producing resolution refutations of unsatisfiability, commonly known as Davis--Putnam procedures, and provide the first asymptotically tight average-case complexity analysis for their behavior on random formulas. In particular, for a simple algorithm in this class, called ordered DLL, we prove that the running time of the algorithm on a randomly generated k-CNF formula with n variables and m clauses is $2^{\Theta(n(n/m)^{1/(k-2)})}$ with probability $1-o(1)$. Finally, we give new lower bounds on $\mbox{res}(F)$, the size of the smallest resolution refutation of F, for a class of formulas representing the pigeonhole principle and for randomly generated formulas. For random formulas, Chvatal and Szemeredi [J. ACM, 35 (1988), pp. 759--768] had shown that random 3-CNF formulas with a linear number of clauses require exponential size resolution proofs, and Fu [On the Complexity of Proof Systems, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1995] extended their results to k-CNF formulas. These proofs apply only when the number of clauses is $\Omega(n \log n)$. We show that a lower bound of the form $2^{n^{\gamma}}$ holds with high probability even when the number of clauses is $n^{(k+2)/4-\epsilon}$.

Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation.

One of the crucial elements in the Internet's success is its ability to adequately control congestion. The paper defines and solves several optimization problems related to Internet congestion control, as a step toward understanding the virtues of the TCP congestion control algorithm currently used and comparing it with alternative algorithms. We focus on regulating the rate of a single unicast flow when the bandwidth available to it is unknown and may change over time. We determine near-optimal policies when the available bandwidth is unchanging, and near-optimal competitive policies when the available bandwidth is changing in a restricted manner under the control of an adversary.

Investigates the class of epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor form the calling to the called players for /spl Theta/(ln n) rounds needs to transmit the rumor /spl Theta/(n ln n) times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, we prove the robustness of this algorithm. On the negative side, we show that any address-oblivious algorithm needs to send /spl Omega/(n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, we give a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i.e. every algorithm that distributes a rumor in O(ln n) rounds needs /spl omega/(n) transmissions.

Custom-designed DNA arrays offer the possibility of simultaneously monitoring thousands of hybridization reactions These arrays show great potential for many medical and scientific applications such as polymorphism analysis and genotyping. Relatively high costs are associated with the need to specifically design and synthesize problem specific arrays. Recently, an alternative approach was suggested that utilizes fixed, universal arrays. This approach presents an interesting design problem—the arrays should contain as many probes as possible, while minimizing experimental errors caused by cross-hybridization. We use a simple thermodynamic model to cast this design problem in a formal mathematical framework. Employing new combinatorial ideas, we derive an efficient construction for the design problem, and prove that our construction is near-optimal.

We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the PRAM(m) model, where p processors communicate through a globally shared memory which can service m requests per unit time, we focus on the trade-off between the amount of local computation and the amount of interprocessor communication required for parallel sorting algorithms. Our main result is a lower bound of $\Omega(\frac{n \log m}{m \log n})$ on the time required to sort n numbers on the exclusive-read and queued-read variants of the PRAM(m). We also show that Leighton's Columnsort can be used to give an asymptotically matching upper bound in the case where m grows as a fractional power of n. The bounds are of a surprising form in that they have little dependence on the parameter p. This implies that attempting to distribute the workload across more processors while holding the problem size and the size of the shared memory fixed will not improve the optimal running time of sorting in this model. We also show that both the lower and the upper bounds can be adapted to bridging models that address the issue of limited communication bandwidth: the LogP model and the bulk-synchronous parallel (BSP) model. The lower bounds provide further convincing evidence that efficient parallel algorithms for sorting rely strongly on high communication bandwidth.

A typical approach to estimate an unknown quantity $\mu$ is to design an experiment that produces a random variable Z, distributed in [0,1] with E[Z]=\mu$, run this experiment independently a number of times, and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0,1]. We describe an approximation algorithm ${\cal A}{\cal A}$ which, given $\epsilon$ and $\delta$, when running independent experiments with respect to any Z, produces an estimate that is within a factor $1+\epsilon$ of $\mu$ with probability at least $1-\delta$. We prove that the expected number of experiments run by ${\cal A}{\cal A}$ (which depends on Z) is optimal to within a constant factor {for every} Z.

Understanding biological systems at the level of genes and proteins is a major challenge. In this paper we represent the interactions among external environmental inputs and genes in a biological system with a graph-theoretic model called a biological pathway. Our goal is to verify a proposed biological pathwayby observing the mRNA levels in the associated biological system under changing external environmental inputs and internal gene perturbations. DNA microarrays allow large-scale comparisons of mRNA levels in pairs of cell cultures. A DNA microarray contains thousands of spots, each containing some portion of a gene. In a di#erential test, mRNAs from two di#erent cell cultures are reverse transcribed to cDNAs, labeled with #uorescent dyes of two di#erent colors, and applied to the array. The relative hybridization levels of the two cDNAs determine the colors of the spots. These colors form the di#erential gene expression data. In this paper we assume that biological pathways can ...

Many computational problems in DNA mapping and sequencing involve determining the relative positions of DNA fragments derived from a target genome region. In the past, many such problems were approached by modeling the fragments as intervals on the real number line and computing the pairwise overlap relation among some or all pairs of intervals. The relative positions of the intervals could then be determined by an error-tolerant interval realization algorithm. In this paper, we present a new model for the problem in which the fragments are once again intervals, but instead of pairwise overlap we compute two alternate relations which we call the inclusion and span relations. We show that in the ideal case in which both relations are known exactly, they lead to an efficient algorithm for interval realization. We also demonstrate how our methods apply to a subproblem in multiple complete digest mapping, allowing us to order the endpoints of clones accurately even in the presence of false...

Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The problem is complicated by uncertainty as to the orientation of the molecules and by erroneous detection of cuts. In this paper we study the problem of constructing a restriction map based on optical mapping data. We give several variants of a polynomial reconstruction algorithm, as well as an algorithm that is exponential in the number of cut sites, and hence is appropriate only for small number of cut sites. We give a simple probabilistic model for data generation and for the errors and prove probabilistic upper and lower bounds on the number of molecules needed by each algorithm in order to obtain a correct map, expressed as a function of the number of cut sites and the error parameters. To the best of our knowledge, this is the first probabilistic analysis of algorithms for the problem. ...

Article Free Access Share on On the complexity of unsatisfiability proofs for random k-CNF formulas Authors: Paul Beame Computer Science, and Engineering, University of Washington, Box 352350, Seattle, WA Computer Science, and Engineering, University of Washington, Box 352350, Seattle, WAView Profile , Richard Karp Computer Science and Engineering, University of Washington Box, 352350, Seattle, WA Computer Science and Engineering, University of Washington Box, 352350, Seattle, WAView Profile , Toniann Pitassi Computer Science Department, University of Arizona, Tucson, AZ Computer Science Department, University of Arizona, Tucson, AZView Profile , Michael Saks Department of Mathematics, Rutgers University, New Brunswick, NJ Department of Mathematics, Rutgers University, New Brunswick, NJView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 561–571https://doi.org/10.1145/276698.276870Online:23 May 1998Publication History 47citation495DownloadsMetricsTotal Citations47Total Downloads495Last 12 Months24Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A class of parallel algorithms for evaluating game trees is presented. These algorithms parallelize a standard sequential algorithm for evaluating AND/OR trees and the α-β pruning procedure for evaluating MIN/MAX trees. It is shown that, uniformly on all instances of uniform AND/OR trees, the parallel AND/OR tree algorithm achieves an asymptotic linear speedup using a polynomial number of processors in the height of the tree. The analysis of linear speedup using more than a linear number of processors is due to J. Harting. A numerical lower bound rigorously establishes a good speedup for the uniform AND/OR trees with parameters that are typical in practice. The performance of the parallel α-β algorithm on best-ordered MIN/MAX trees is analyzed.

Multiple Complete Digest (MCD) mapping is a method of determining the locations of restriction sites along a target DNA strand. The resulting restriction map has many potential applications in DNA sequencing and genetics. In this work, we present a heuristic for fragment identification, one step in the process of constructing a MCD map. We assume that we are given information about one or more complete digestions of a clone library covering the area to be mapped. From this data, we identify groups of restriction fragments on different clones that correspond to the same region of the target DNA. Maintaining certain constraints on the groups allows us to form a system of simple linear inequalities whose solution yields the desired map. We demonstrate the effectiveness of our heuristic on real data provided by the Genome Center at the University of Washington.

No abstract available.

The Internet offers unprecedented access to information. At present most of this information is free, but information providers ore likely to start charging for their services in the near future. With that in mind this paper introduces the following information access problem: given a collection of n information sources, each of which has a known time delay, dollar cost and probability of providing the needed information, find an optimal schedule for querying the information sources. We study several variants of the problem which differ in the definition of an optimal schedule. We first consider a cost model in which the problem is to minimize the expected total cost (monetary and time) of the schedule, subject to the requirement that the schedule may terminate only when the query has been answered or all sources have been queried unsuccessfully. We develop an approximation algorithm for this problem and for an extension of the problem in which more than a single item of information is being sought. We then develop approximation algorithms for a reward model in which a constant reward is earned if the information is successfully provided, and we seek the schedule with the maximum expected difference between the reward and a measure of cost. The monetary and time costs may either appear in the cost measure or be constrained not to exceed a fixed upper bound; these options give rise to four different variants of the reward model.

A typical approach to estimate an unknown quantity /spl mu/ is to design an experiment that produces a random variable Z distributed in [O,1] with E[Z]=/spl mu/, run this experiment independently a number of times and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0,1]. We describe an approximation algorithm AA which, given /spl epsiv/ and /spl delta/, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+/spl epsiv/ of /spl mu/ with probability at least 1-/spl delta/. We prove that the expected number of experiments ran by AA (which depends on Z) is optimal to within a constant factor for every Z.

This paper introduces the bit vector intersection problem: given a large collection of sparse bit vectors, find all the pairs with at least t ones in common for a given input parameter t. The assumption is that the number of ones common to any two vectors is significantly less than t, except for an unknown set of O(n) pairs. This problem has important applications in DNA physical mapping, clustering, and searching for approximate dictionary matches. We present two randomized algorithms that solve this problem with high probability and in sub-quadratic expected time. One of these algorithms is based on a recursive tree-searching procedure, and the other on hashing. We analyze the tree scheme in terms of branching processes, while our analysis of the hashing scheme is based on Markov chains. Since both algorithms have similar asymptotic performance, we also examine experimentally their relative merits in practical situations. We conclude by showing that a fundamental problem arising in the Human Genome Project is captured by the bit vector intersection problem described above and hence can be solved by our algorithms.

We study the problem of sorting on a parallel computer with limited communication bandwidth.By using the recently proposed PRAM (m) model, where p processors communicate through a small, globally shared memory consisting of m bits, we focus on the trade-off between the amount of local computation and the amount of inter-processor communication required for parallel sorting algorithms.We prove a lower bound of Q(-) on the time to sort n numbers in an exclusive-read variant of the PRAM(m) model.We show that Leighton's Columnsort can be used to give an asymptotically matching upper bound in the case where m grows as a fractional power of n.The bounds are of a surprising form, in that they have little dependence on the parameter p.This implies that attempting to distribute the workload across more processors while holding the problem size and the size of the shared memory fixed will not improve the optimal running time of sorting in this model.We also show that both the upper and the lower bound can be adapted to bridging models that address the issue of limited communication bandwidth: the LogP model and the BSP model.The lower bounds provide convincing evidence that efficient parallel algorithms for sorting rely strongly on high communication bandwidth.

A partial digestion of DNA (e.g. cosmid. Lambda, YAC, chromosome) is performed and the lengths of thoses fragments which hybridize to a labeled probe are measured using gel electrophoresis. We give an efficient algorithm that takes as input this experimental data and proposes one or more candidate solutions. Each solution designates the location of each restriction site and specifies the endpoints of each fragment. (Further experiments can then be designed to select the correct solution from this small set of candidates.) The algorithm works well even when the experiment gives inexact values for the lengths.

This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and the edge player chooses an edge e. The payoff to the edge player is $\textit{cost} (T, e)$, defined as follows: If e lies in the tree T then $\textit{cost}(T, e) = 0$; if e does not lie in the tree then $\textit{cost}(T, e) = cycle(T, e)/w(e)$, where $w(e)$ is the weight of edge e and $\textit{cycle}(T, e)$ is the weight of the unique cycle formed when edge e is added to the tree T. The main result is that the value of the game on any n-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log \log n}))$. It is conjectured that the value of the game is $O(\log n)$. The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length $w(e)$. It is shown that, if the value of the game on G is $\textit{Val}(G, w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + \textit{Val}(G, w))$ against any oblivious adversary. Thus, on any n-vertex road network, there is a randomized algorithm for the k-server problem that is $k \cdot \exp(O(\sqrt{\log n \log \log n}))$ competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any n-vertex weighted, connected multigraph, the algorithm constructs a spanning tree T such that the average, over all edges e, of $\textit{cost}(T, e)$ is less than or equal to $\exp(O(\sqrt{\log n \log \log n}))$. This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.

We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem $\textit{ATSP}(M)$ and the value of its assignment relaxation $\textit{AP}(M)$. We assume here that the costs are given by an $n \times n$ matrix M whose entries are independently and identically distributed. We focus on the relationship between $Pr(\textit{ATSP}(M) = \textit{AP}(M))$ and the probability $p_{n}$ that any particular entry is zero. If $np_{n} \rightarrow \infty $ with n then we prove that $\textit{ATSP}(M) = \textit{AP}(M)$ with probability 1-o(1). This is shown to be best possible in the sense that if $np (n) \rightarrow c,\, c > 0$ and constant, then $Pr(\textit{ATSP}(M) = \textit{AP}(M)) < 1 - \phi (c)$ for some positive function $\phi$. Finally, if $np_{n} \rightarrow 0$ then $Pr(\textit{ATSP}(M) = \textit{AP}(M)) \rightarrow 0$.

This paper is concerned with recurrence relations that arise frequently m the analysis of divide-and-conquer algorithms.In order to solve a problcm instance of size x, such an algorlthm invests an amount of work a(x) to break the problem mto subproblems of sizes h l(x), hz(x), . . . .lr~(,r), and then proceeds to solve the subproblems.Our particular interest is in the case where the sizes hr(.r) are random variables; th]s may occur either because of randomization within the algorlthm or because the instances to be solved are assumed to be drawn from a probability distribution.When the h are random variables the running time of the algorithm on instances of size x is also a random variable T(x).We give several easy-to-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of T(x), and present a number of typical applications of these bounds to the analysis of algorithms.The proofs of tbe bounds are based on an interesting analysis of optimal strategies in certain gambling games.

A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of formal loopholes, rather than rewarding development of techniques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. it is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers. Such a model must strike a balance between detail and simplicity in order to reveal important bottlenecks without making analysis of interesting problems intractable. The model is based on four parameters that specify abstractly the computing bandwidth, the communication bandwidth, the communication delay, and the efficiency of coupling communication and computation. Portable parallel algorithms typically adapt to the machine configuration, in terms of these parameters. The utility of the model is demonstrated through examples that are implemented on the CM-5.

In many distributed-memory parallel computers the only built-in communication primitive is point-to-point message transmission, and more powerful operations suchas broadcast and synchronization must be realized using this primitive. Within the LogP model of parallel computation we present algorithms that yield optimal communication schedulesfor several broadcastand synchronization operations. Most of our algorithms are the absolutely best possible in that not even the constant factors can be improved upon. For one particular broadcast problem, called continuous broadcast, the optimality of our algorithm is not yet completely proven, although proofs have been achieved for a certain range of parameters. We also devise an optimal algorithm for summing or, more generally, applying a non-commutative associative binary operator to a set of operands. 1 Introduction Most models of parallel computation reflect the communication bottlenecks of real parallel machines inadequately. The PRAM [11],...

Article Free Access Share on Mapping the genome: some combinatorial problems arising in molecular biology Author: Richard M. Karp View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 278–285https://doi.org/10.1145/167088.167170Published:01 June 1993Publication History 65citation1,101DownloadsMetricsTotal Citations65Total Downloads1,101Last 12 Months34Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Universal randomized methods for parallelizing sequential backtrack search and branch-and-bound computation are presented.These methods execute on message-passing multiprocessor systems, and require no global data structures or complex communication protocols.For backtrack search, it is shown that, uniformly on all instances, the method described in this paper is likely to yield a speed-up within a small constant factor from optimal, when all solutions to the problem instance are required.For branch-and-bound computation, it is shown that, uniformly on all instances, the execution time of this method is unlikely to exceed a certain inherent lower bound by more than a constant factor.These randomized methods demonstrate the effectiveness of randomization in distributed parallel computation.

Let A be an $n \times n$ matrix with 0-1 valued entries, and let ${\operatorname{per}}(A)$ be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a “good in the relative sense” estimate of ${\operatorname{per}}(A)$ and has running time ${\operatorname{poly}}(n)2^{{n / 2}} $, where ${\operatorname{poly}}(n)$ denotes a function that grows polynomially with n.

In the unidirectional conversion problem an on-line player is given the task of converting dollars to yen over some period of time. Each day, a new exchange rate is announced and the player must decide how many dollars to convert. His goal is to minimize the competitive ratio. defined as sup/sub E/ (P/sub OPT/(E)/P/sub X/E) where E ranges over exchange rate sequences. P/sub OPT/(E) is the number of yen obtained by an optimal off-line algorithm, and Px(E) is the number of yen obtained by the on-line algorithm X. The authors also consider a continuous version of the problem. in which the exchange rate varies over a continuous time interval. The on-line line players a priori information about the fluctuation of exchange rates distinguishes different variants of the problem. For three variants they show that a simple threat-based strategy is optimal for the on-line player and determine its competitive ratio. They also derive and analyze an optimal policy for the on-line player when he knows the probability distribution of the maximum value that the exchange rate will reach. Finally, they consider a bidirectional conversion problem, which the player may trade dollars for yen or yen for dollars.>

We present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (DMM) with optimal expected delay O(log log (n)) per step of simulation. The time bound for the delay is guaranteed with overwhelming probability. The algorithm is based on hashing and uses a novel simulation scheme. The best previous simulations use a simpler scheme based on hashing and have much larger expected delay: Θ(log(n)/log log (n)) for the simulation of an n-processor PRAM on an n processor DMM, and Θ(log(n)) in the case where the simulation preserves the processor-time product.

An acyclic directed network with n sources and m sinks is called a generalized connector if, for any request pattern in which each sink asks to be connected to some source, the required configuration of noninterfering connecting paths can be set up. This paper presents new families of two- and three-stage connection networks and gives a method of establishing that particular networks in these families are generalized connectors. This method is based on the Erdös probabilistic method and consists of two steps: 1. First it is proven that a given network is a generalized connector provided that certain events in a probability space $\Omega $ are of sufficiently low probability. 2. Then it is shown that the probabilities of these events are indeed sufficiently small.For the family of designs presented in Section 5, the second step is accomplished by explicitly calculating the probabilities of the events in question, using dynamic programming; these calculations provide rigorous proofs that the designs are correct. However, for the more economical designs of Section 6, the probabilities of the events in question are not calculated exactly, but instead are estimated by drawing pseudo-random samples from the probability space $\Omega $. Thus, we have only a “statistical proof” (albeit a very convincing one) of the correctness of these designs. For certain choices of n and m the most efficient three-stage generalized connectors currently known are obtained.

No abstract available.

Article Free Access Share on An optimal algorithm for on-line bipartite matching Authors: R. M. Karp University of California at Berkeley & International Computer Science Institute University of California at Berkeley & International Computer Science InstituteView Profile , U. V. Vazirani Cornell University Cornell UniversityView Profile , V. V. Vazirani View Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990Pages 352–358https://doi.org/10.1145/100216.100262Published:01 April 1990Publication History 439citation3,555DownloadsMetricsTotal Citations439Total Downloads3,555Last 12 Months519Last 6 weeks66 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on On parallel evaluation of game trees Authors: R. M. Karp Computer Science Division, University of California, Berkeley, CA Computer Science Division, University of California, Berkeley, CAView Profile , Y. Zhang Computer Science Division, University of California, Berkeley, CA Computer Science Division, University of California, Berkeley, CAView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 409–420https://doi.org/10.1145/72935.72979Published:01 March 1989Publication History 13citation316DownloadsMetricsTotal Citations13Total Downloads316Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a universal randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. The method executes on a message-passing multiprocessor system, and requires no global data structures or complex communication protocols. We show that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.

We consider the problem of answering a series of on-line queries on a static data set. The conventional approach to such problems involves a preprocessing phase which constructs a data structure with good search behavior. The data structure representing the data set then remains fixed throughout the processing of the queries. Our approach involves dynamic or query-driven structuring of the data set; our algorithm processes the data set only when doing so is required for answering a query. A data structure constructed progressively in this fashion is called a deferred data structure. We develop the notion of deferred data structures by solving the problem of answering membership queries on an ordered set. We obtain a randomized algorithm which achieves asymptotically optimal performance with high probability. We then present optimal deferred data structures for the following problems in the plane: testing convex-hull membership, half-plane intersection queries and fixed-constraint multi-objective linear programming. We also apply the deferred data structuring technique to multi-dimensional dominance query problems.

We study the expected behavior of the FFD binpacking algorithm applied to items whose sizes are distributed in accordance with a Poisson process with rate N on the interval [0,1/2] of item sizes. By viewing the algorithm as a succession of queueing processes we show that the expected wasted space for FFD bin-packing is bounded above by 9.4 bins, independent of N. We extend this upper bound to a FFD bin-packing of items in accordance with a non-homogeneous Poisson process with a nonincreasing intensity function λ(t) on [0,1/2].

In [KUW1] we have proposed the setting of independence systems to study the relation between the computational complexity of search and decision problems. The universal problem that captures this relation, which we termed the S-search problem, is: "Given an oracle for the input system, find a maximal independent subset in it". Many interesting and important search problems can be described by a special class of independence systems, called matroids. This paper is devoted to die complexity of the S- search problem for matroids. Our main result is a lower bound on any probabilistic algorithm for the S-search problem that acquires information about the input system by interrogating an independence oracle. We prove that the expected time of any such probabilistic algorithm that uses a sub-exponential number of processors is Ω(n1/3-ε). This is one of the first nontrivial, super-logarithmic lower bounds on a randomized parallel computation. It implies that in our model of computation Random-NC is strictly contained in P. Another consequence of the lower bound is that the O(√n) time probabilistic upper bound for arbitrary independence systems, presented in [KUW1], is close to optimal and cannot be significantly improved, even for matroids. However, fills O(√n) upper bound can be improved in a different sense for matroids -it can be made deterministic, still with polynomially many processors. Finally, we show that the lower bound can be beaten for the special case of graphic matroids. Here, the S-search problem is simply to find a spanning forest of a graph, when the algorithm cannot see the graph, but can only ask whether subsets of edges are forests or not. We give an O(logn) time deterministic parallel algoritlun that uses nO(logn) processors. From the upper bounds on parallel time above we deduce similar bounds (up to a poly-log factor) on thc sequential space required by a deterministic Turing machine with an independence oracle to solve the S-search problem.

In this paper we show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC: i.e., lhe problem is solvable in polylog lime by a randomized parallel algorithm using a polynomial-bounded number of processors.We also show that several related problems lie in Random NC.These include: (9 Construcling a pcrfccl malchin$; of maximum wcighl in a gmph whose edge weights are given in unary notalion; t Kcxatuh suppoiicd by NW Grant #DCK-&111954.$ Rcscmh suppwl~xl by a Wcimnnti Posl-Docloral Qllowsbip, :1nt1 by IhI KI'A GCWI NOo39-U-C-1036.vt Kcuc:erh suppolor~rd in, part hy l)hKPh Gmnt NOOO39-82-C 0235.

From the point of view of sequential polynomial time computation, the answer to the question in the title is 'yes'. The process of self-reducibility is a linear time Turing (oracle) reduction from a given combinatorial search problem to an appropriately defined decision problem.

A parallel algorithm is presented that accepts as input a graph G and produces a maximal independent set of vertices in G . On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O ((log n ) 4 ) time and uses O (( n /(log n )) 3 ) processors, where n is the number of vertices in G . The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.

This paper gives probabilistic analyses of two kinds of multidimensional bin packing problems: vector packing and rectangle packing. In the vector packing problem each of the d dimensions can be interpreted as a resource. A given object i consumes aijunits of the jthresource, and the objects packed in any given bin may not collectively consume more than one unit of any resource. Subject to this constraint, the objects are to be packed into a minimum number of bins. The rectangle packing problem is more geometric in character. The ithobject is a d-dimensional box whose jthside is of length aij, and the goal is to pack the objects into a minimum number of cubical boxes of side 1. We study these problems on the assumption that the aijare drawn independently from the uniform distribution over [0,1]. We study a vector packing heuristic called VPACK that tries to place two objects in each bin and a rectangle packing heuristic called RPACK that tries to pack one object into each of the 2d corners of each bin. We show that each of these heuristics tends to produce packings in which very little of the capacity of the bins is wasted. In the case of rectangle packing, we show that the results can be extended to a wide class of distributions of the piece sizes.

A parallel algorithm is presented that accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in G((10gn)~) time and uses 0((n/(logn))3) processors, where n is the number of vertices in G.The algorithm has several novel features that may find other applications.These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a "dynamic pigeonhole principle" that generalizes the conventional pigeonhole principle.

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number ε, and produces as output a packing using as most (1 + ε) OPT(I) + O(ε-2) bins. Its execution time is O(ε-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables.

We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP = co-NP—a very unlikely event. We also apply the ellipsoid method for linear programming to show that a combinatorial optimization problem is solvable in polynomial time if and only if it admits a small generator of violated inequalities.

We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP = co-NP -- a very unlikely event. We also apply the ellipsoid method for linear programming to show that a combinatorial optimization problem is solvable in polynomial time if and only if it admits a small generator of violated inequalities.

It is well known that every set in P has small circuits [13]. Adleman [1] has recently proved the stronger result that every set accepted in polynomial time by a randomized Turing machine has small circuits. Both these results are typical of the known relationships between uniform and nonuniform complexity bounds. They obtain a nonuniform upper bound as a consequence of a uniform upper bound.

Researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (Exceptions include the work of Angluin and Valiant [1], Karp [7], and Schnorr [9].) In this paper we analyze the expected running time of four algorithms for solving graph connectivity problems. Our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs.

Abstract We give an algorithm to solve the m‐source, n‐destination assignment problem in expected time O(mn log n) under the assumption that the edge costs are independent random variables and the costs of the edges incident with any given source are identically distributed. The algorithm achieves its efficiency through an unusual application of priority queues.

We present an algorithm for the approximate solution of the nonsymmetric n-city traveling-salesman problem. An instance of this problem is specified by a $n \times n$ distance matrix $D = (d_{ij} )$. The algorithm first solves the assignment problem for the matrix D, and then patches the cycles of the optimum assignment together to form a tour. The execution time of the algorithm is comparable to the time required to solve an $n \times n$ assignment problem. If the distances $d_{ij} $ are drawn independently from a uniform distribution then, with probability tending to 1, the ratio of the cost of the tour produced by the algorithm to the cost of an optimum tour is $ < 1 + \varepsilon (n)$, where $\varepsilon (n)$ goes to zero as $n \to \infty $. Hence the method tends to give nearly optimal solutions when the number of cities is extremely large.

A large class of classical combinatorial problems, including most of the difficult problems in the literature of network flows and computational graph theory, are shown to be equivalent, in the sense that either all or none of them can be solved in polynomial time. Moreover, they are solvable in polynomial time if and only if every problem solvable by a polynomial‐depth backtrack search is also solvable by a polynomial‐time algorithm. The technique of deriving these results through problem transformations is explained, and some comments are made as to the probable effect of these results on research in the field of combinatorial algorithms.

We consider the problem of placing records in a 2-dimensional storage array so that expected distance between consecutive references is minimized. A simple placement heuristic which uses only relative frequency of access for different records is shown to be within an additive constant of optimal when distance is measured by the Euclidean metric. For the rectilinear and maximum metrics, we show that there is no such heuristic. For the special case in which all access probabilities are equal, however, heuristics within an additive constant of optimal do exist, and their implementation requires solution of differential equations for which we give numerical solutions.

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + n)\sqrt n $.

In this paper we look at a number of matching problems and devise general techniques for attacking such problems. In particular, we describe a strategy for constructing efficient algorithms for solving two types of matching problems. We use this strategy to develop explicit algorithms for these two problems applied to strings (where the patterns are substrings) and arrays (where the patterns are subarrays or blocks). We also develop algorithms for these and related problems for trees, where the patterns are subtrees. Certain special cases of these algorithms are also discussed.

article Free Access Share on Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems Authors: Jack Edmonds Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, CanadaView Profile , Richard M. Karp College of Engineering, Operations Research Center, University of California, Berkeley, California College of Engineering, Operations Research Center, University of California, Berkeley, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 19Issue 2April 1972 pp 248–264https://doi.org/10.1145/321694.321699Published:01 April 1972Publication History 1,682citation6,930DownloadsMetricsTotal Citations1,682Total Downloads6,930Last 12 Months607Last 6 weeks140 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract Edmonds [1] has given an algorithm for constructing a maximum‐weight branching in a weighted directed graph. His proof that the algorithm is correct is based on linear programming theory, and establishes as a by‐product that a certain polyhedron has integer vertices. Here we give a direct combinatorial proof of the correctness of the algorithm.

Any sequential machine M represents a function f M from input sequences to output symbols. A function f is representable if some finite-state sequential machine represents it. The function f M is called an n-th order approximation to a given function f if f M is equal to f for all input sequences of length less than or equal to n . It is proved that, for an arbitrary nonrepresentable function f , there are infinitely many n such that any sequential machine representing an n th order approximation to f has more than n /2 + 1 states. An analogous result is obtained for two-way sequential machines and, using these and related results, lower bounds are obtained for two-way sequential machines and, using these and related results, lower bounds are obtained on the amount of work tape required online and offline Turing machines that compute nonrepresentable functions.

A set equations in the quantities a i ( p ), where i = 1, 2, · · ·, m and p ranges over a set R of lattice points in n -space, is called a system of uniform recurrence equations if the following property holds: If p and q are in R and w is an integer n -vector, then a i ( p ) depends directly on a j ( p - w ) if and only if a i ( q ) depends directly on a j ( q - w ). Finite-difference approximations to systems of partial differential equations typically lead to such recurrence equations. The structure of such a system is specified by a dependence graph G having m vertices, in which the directed edges are labeled with integer n -vectors. For certain choices of the set R , necessary and sufficient conditions on G are given for the existence of a schedule to compute all the quantities a i ( p ) explicitly from their defining equations. Properties of such schedules, such as the degree to which computation can proceed “in parallel,” are characterized. These characterizations depend on a certain iterative decomposition of a dependence graph into subgraphs. Analogous results concerning implicit schedules are also given.

A procedure for index register allocation is described. The rules of this procedure are shown to yield an optimal allocation for “straight line” programs.

This paper is an extension of the work of Hartmanis and Stearns on sequential machine state assignments with reduced dependence. In Section II the critical partition pairs of transition-incomplete sequential machines are defined, and methods are given for computing them. Section III pursues certain combinatorial problems associated with the construction of assignments with reduced dependence, once the critical partition pairs are known. The algorithms derived in this paper provide the nucleus of a systematic procedure for the construction of economical state assignments.

This paper gives a method for constructing minimum-redundancy prefix codes for the general discrete noiseless channel without constraints. The costs of code letters need not be equal, and the symbols encoded are not assumed to be equally probable. A solution had previously been given by Huffman [10] in 1952 for the special case in which all code letters are of equal cost. The present development is algebraic. First, structure functions are defined, in terms of which necessary and sufficient conditions for the existence of prefix codes may be stated. From these conditions, linear inequalities are derived which may be used to characterize prefix codes. Gomory's integer programming algorithm is then used to construct optimum codes subject to these inequalities; computational experience is presented to demonstrate the practicability of the method. Finally, some additional coding problems are discussed and a problem of classification is treated.