We consider the problem of scheduling $m$ jobs on $n$ unrelated strategic machines to minimize the maximum load of any machine, but the machines are strategic and may misreport processing times to minimize their own load. The pioneering work of Nisan and Ronen gave an $n$-approximate deterministic strategyproof mechanism for this setting, and this was recently shown to be best possible by the breakthrough results of Christodoulou et al. This large approxation guarantee begs the question: how can we avoid these large worst-case results. In this work, we use the powerful framework of algorithms with (machine-learned) predictions to bypass these strong impossibility results. We show how we can predict $O(m+n)$ values to obtain a deterministic strategyproof algorithm whose makespan is within a constant factor of the optimal makespan when the predictions are correct, and $O(n)$ times the optimum no matter how poor the predictions are.

Competitive equilibrium is a fundamental concept in the study of markets, describing stable outcomes that can emerge from agents' trading. Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and Constant Elasticity of Substitution (CES) utilities. However, homogeneous utilities remain a relatively restrictive subset compared to the diverse preferences that economists have considered. For instance, even the intuitive separable utilities of the form u (x) = Σj uj(xj) are generally not homogeneous. This gap motivates the open question: to what extent can the proportional response dynamics be applied to markets with non-homogeneous utility functions?

To guarantee all agents are matched in general, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions: - Why does it work well? - Which proposals should agents include in their preference lists? We study these questions in a model, introduced by Lee [Lee, 2016], with preferences based on correlated cardinal utilities: these utilities are based on common public ratings of each agent together with individual private adjustments. Lee showed that for suitable utility functions, in large markets, with high probability, for most agents, all stable matchings yield similar valued utilities. By means of a new analysis, we strengthen Lee’s result, showing that in large markets, with high probability, for all but the agents with the lowest public ratings, all stable matchings yield similar valued utilities. We can then deduce that for all but the agents with the lowest public ratings, each agent has an easily identified length O(log n) preference list that includes all of its stable matches, addressing the second question above. We note that this identification uses an initial communication phase. We extend these results to settings where the two sides have unequal numbers of agents, to many-to-one settings, e.g. employers and workers, and we also show the existence of an ε-Bayes-Nash equilibrium in which every agent makes relatively few proposals. These results all rely on a new technique for sidestepping the conditioning between the tentative matching events that occur over the course of a run of the Deferred Acceptance algorithm. We complement these theoretical results with an experimental study.

Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks.

We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value νi,j for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the νi,j values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.

We extend a recently developed framework for analyzing asynchronous coordinate descent algorithms to show that an asynchronous version of tatonnement, a fundamental price dynamic widely studied in general equilibrium theory, converges toward a market equilibrium for Fisher markets with CES utilities or Leontief utilities, for which tatonnement is equivalent to coordinate descent.

We seek to understand when heterogeneity in agent preferences yields improved outcomes in terms of overall cost. That this might be hoped for is based on the common belief that diversity is advantageous in many multi-agent settings. We investigate this in the context of routing. Our main result is a sharp characterization of the network settings in which diversity always helps, versus those in which it is sometimes harmful. Specifically, we consider routing games, where diversity arises in the way that agents trade-off two criteria (such as time and money, or, in the case of stochastic delays, expectation and variance of delay). Our main contributions are: 1) A participant-oriented measure of cost in the presence of agent diversity; 2) A full characterization of those network topologies for which diversity always helps, for all latency functions and demands.

A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify natural distributed algorithms that converge quickly to an equilibrium. This paper established new convergence results for two generalizations of proportional response in Fisher markets with buyers having CES utility functions. The starting points are respectively a new convex and a new convex-concave formulation of such markets. The two generalizations correspond to suitable mirror descent algorithms applied to these formulations. Several of our new results are a consequence of new notions of strong Bregman convexity and of strong Bregman convex-concave functions, and associated linear rates of convergence, which may be of independent interest. Among other results, we analyze a damped generalized proportional response and show a linear rate of convergence in a Fisher market with buyers whose utility functions cover the full spectrum of CES utilities aside the extremes of linear and Leontief utilities; when these utilities are included, we obtain an empirical $O(1/T)$ rate of convergence.

We study the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents' valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our main result is the first efficient constant-factor approximation algorithm for this objective. We first observe that the integrality gap of the natural fractional relaxation is exponential, so we propose a different fractional allocation which implies a tighter upper bound and, after appropriate rounding, yields a good integral allocation. An interesting contribution of this work is the fractional allocation that we use. The relaxation of our problem can be solved efficiently using the Eisenberg--Gale program, whose optimal solution can be interpreted as a market equilibrium with the dual variables playing the role of item prices. Using this market-based interpretation, we define an alternative equilibrium allocation where the amount of spending that can go into any given item is bounded, thus keeping the highly priced items under-allocated and forcing the agents to spend on lower priced items. The resulting equilibrium prices reveal more information regarding how to assign items so as to obtain a good integral allocation.

No abstract available.

We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known O(Q+S · (M/B)) caching cost for the randomized work stealing (RWS) scheduler, where S is the number of steals, Q is the sequential caching cost, and M and B are the cache size and block (or cache line) size respectively.

As is well known, many classes of markets have efficient equilibria, but this depends on agents being non-strategic, i.e. that they declare their true demands when offered goods at particular prices, or in other words, that they are price-takers. An important question is how much the equilibria degrade in the face of strategic behavior, i.e. what is the Price of Anarchy (PoA) of the market viewed as a mechanism?

We study the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents' valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our main result is the first efficient constant-factor approximation algorithm for this objective. We first observe that the integrality gap of the natural fractional relaxation is exponential, so we propose a different fractional allocation which implies a tighter upper bound and, after appropriate rounding, yields a good integral allocation.

Two classes of distributions that are widely used in the analysis of Bayesian auctions are the Monotone Hazard Rate (MHR) and Regular distributions. They can both be characterized in terms of the rate of change of the associated virtual value functions: for MHR distributions the condition is that for values $$v < v'$$ , $$\phi (v') - \phi (v) \ge v' - v$$ , and for regular distributions, $$\phi (v') - \phi (v) \ge 0$$ . Cole and Roughgarden introduced the interpolating class of $$\alpha $$ -Strongly Regular distributions ( $$\alpha $$ -SR distributions for short), for which $$\phi (v') - \phi (v) \ge \alpha (v' - v)$$ , for $$0 \le \alpha \le 1$$ . In this paper, we investigate five distinct auction settings for which good expected revenue bounds are known when the bidders’ valuations are given by MHR distributions. In every case, we show that these bounds degrade gracefully when extended to $$\alpha $$ -SR distributions. For four of these settings, the auction mechanism requires knowledge of these distribution(s) (in the other setting, the distributions are needed only to ensure good bounds on the expected revenue). In these cases we also investigate what happens when the distributions are known only approximately via samples, specifically how to modify the mechanisms so that they remain effective and how the expected revenue depends on the number of samples.

In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal of this paper is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue.

Two equal-length strings, or two equal-sized two-dimensional texts, parameterize match ( p-match ) if there is a one-one mapping (relative to the alphabet) of their characters. Two-dimensional parameterized matching is the task of finding all m × m substrings of an n × n text that p-match an m × m pattern. This models searching for color images with changing of color maps, for example. We present two algorithms that solve the two-dimensional parameterized matching problem. The time complexities of our algorithms are O ( n 2 log 2 m ) and O ( n 2 + m 2.5 polylog( m )). Our algorithms are faster than the O ( n 2 m log 2 m log log m ) time algorithm for this problem of Amir et al. [2006]. A key step in both of our algorithms is to count the number of distinct characters in every m × m substring of an n × n string. We show how to solve this problem in O ( n 2 ) time. This result may be of independent interest.

This paper analyzes the overhead due to false sharing when parallel tasks are scheduled using randomized work stealing (RWS). We obtain high-probability bounds on the cache miss overhead, including the overhead due to false sharing, for several parallel cache-efficient algorithms when scheduled using RWS. These include algorithms for fundamental problems, such as matrix computations, FFT, sorting, basic dynamic programming, list ranking and graph connected components. Our main technical contribution, from which these results follow, is the derivation of nontrivial high-probability bounds on the number of steals incurred by these algorithms in the presence of false sharing, when using RWS.

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option.

Tatonnement is a simple and natural rule for updating prices in Exchange (Arrow-Debreu) markets. In this paper we define a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex potential function whose gradient is always equal to the negative of the excess demand and we call it Convex Potential Function (CPF) markets. We show the following results. CPF markets contain the class of Eisenberg Gale (EG) markets, defined previously by Jain and Vazirani. The subclass of CPF markets for which the demand is a differentiable function contains exactly those markets whose demand function has a symmetric negative semi-definite Jacobian. We define a family of continuous versions of tatonnement based on gradient descent using a Bregman divergence. As we show, all processes in this family converge to an equilibrium for any CPF market. This is analogous to the classic result for markets satisfying the Weak Gross Substitutes property. A discrete version of tatonnement converges toward the equilibrium for the following markets of complementary goods; its convergence rate for these settings is analyzed using a common potential function. Fisher markets in which all buyers have Leontief utilities. The tatonnement process reduces the distance to the equilibrium, as measured by the potential function, to an ε fraction of its initial value in O(1/ε) rounds of price updates. Fisher markets in which all buyers have complementary CES utilities. Here, the distance to the equilibrium is reduced to an ε fraction of its initial value in O(log(1/ε)) rounds of price updates.

We consider algorithms for a multicore environment in which each core has its own private cache and false sharing can occur. False sharing happens when two or more processors access the same block (i.e., cache-line) in parallel, and at least one processor writes into a location in the block. False sharing causes different processors to have inconsistent views of the data in the block, and many of the methods currently used to resolve these inconsistencies can cause large delays. We analyze the cost of false sharing both for variables stored on the execution stacks of the parallel tasks and for output variables. Our main technical contribution is to establish a low cost for this overhead for the class of multithreaded block-resilient HBP (Hierarchical Balanced Parallel) computations. Using this and other techniques, we develop block-resilient HBP algorithms with low false sharing costs for several fundamental problems including scans, matrix multiplication, FFT, sorting, and hybrid block-resilient HBP algorithms for list ranking and graph connected components. Most of these algorithms are derived from known multicore algorithms, but are further refined to achieve a low false sharing overhead. Our algorithms make no mention of machine parameters, and our analysis of the false sharing overhead is mostly in terms of the the number of tasks generated in parallel during the computation, and thus applies to a variety of schedulers.

This paper continues the study, initiated by Cole and Fleischer in [Cole and Fleischer 2008], of the behavior of a tatonnement price update rule in Ongoing Fisher Markets. The prior work showed fast convergence toward an equilibrium when the goods satisfied the weak gross substitutes property and had bounded demand and income elasticities.

Abstract We study the price of anarchy of selfish routing with variable traffic rates and when the path cost is a nonadditive function of the edge costs. Nonadditive path costs are important, for example, in networking applications, where a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. We prove the following results. In multicommodity networks, the worst‐case price of anarchy under the ℓp path cost with 1 < p ≤∞ can be dramatically larger than under the standard ℓ1 path cost. In single‐commodity networks, the worst‐case price of anarchy under the ℓp path cost with 1 < p < ∞ is no more than with the standard ℓ1 path norm. (A matching lower bound follows trivially from known results.) This upper bound also applies to the ℓ∞ path cost if and only if attention is restricted to the natural subclass of equilibria generated by distributed shortest path routing protocols. For a natural cost‐minimization objective function, the price of anarchy with endogenous traffic rates (and under any ℓp path cost) is no larger than that in fixed‐demand networks. Intuitively, the worst‐case inefficiency arising from the “tragedy of the commons” is no more severe than that from routing inefficiencies. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

We study coordination mechanisms aiming to minimize the weighted sum of completion times of jobs in the context of selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain these approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. The method entails mapping strategy vectors into a carefully chosen inner product space; costs are shown to correspond to the norm in this space, and the Nash condition also has a simple description. With this structure in place, we are able to prove a number of results, as follows. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given fixed assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed.

Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, this paper formalizes the setting of Ongoing Markets, by contrast with the classic market scenario, which we term One-Time Markets. The Ongoing Market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. As such, it appears to be a more plausible model of actual markets.

An edge of a graph is light when the sum of the degrees of its end‐vertices is at most 13. The well‐known Kotzig theorem states that every 3‐connected planar graph contains a light edge. Later, Borodin [J. Reine Angew. Math., 394 (1989), pp. 180–185] extended this result to the class of planar graphs of minimum degree at least 3. We deal with generalizations of these results for planar graphs of minimum degree 2. Borodin, Kostochka, and Woodall [J. Combin. Theory Ser. B, 71 (1997), pp. 184–204] showed that each such graph contains a light edge or a member of two infinite sets of configurations, called 2‐alternating cycles and 3‐alternators. This implies that planar graphs with maximum degree $\Delta \geq 12$ are $\Delta$‐edge‐choosable. We prove a similar result with 2‐alternating cycles and 3‐alternators replaced by five fixed bounded‐sized configurations called crowns. This gives another proof of $\Delta$‐edge‐choosability of planar graphs with $\Delta \geq 12$. However, we show efficient choosability; i.e., we describe a linear‐time algorithm for $\max\{\Delta,12\}$‐edge‐list‐coloring planar graphs. This extends the result of Chrobak and Yung [J. Algorithms, 10 (1989), pp. 35–51].

We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1+ε)-approximate nearest neighbor in time O(log n) + (1/ε)O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.

The representation of objects in images as tree structures is of great interest to vision, as they can represent articulated objects such as people as well as other structured objects like arteries in human bodies, roads, circuit board patterns, etc. Tree structures are often related to the symmetry axis representation of shapes, which captures their local symmetries. Algorithms have been introduced to detect (i) open contours in images in quadratic time (ii) closed contours in images in cubic time, and (iii) tree structures from contours in quadratic time. The algorithms are based on dynamic programming and single source shortest path algorithms. However, in this paper, we show that the problem of finding tree structures in images in a principled manner is a much harder problem. We argue that the optimization problem of finding tree structures in images is essentially equivalent to a variant of the Steiner tree problem, which is NP-hard. Nevertheless, an approximate polynomial-time algorithm for this problem exists: we apply a fast implementation of the Goemans-Williamson approximate algorithm to the problem of finding a tree representation after an image is transformed by a local symmetry mapping. Examples of extracting tree structures from images illustrate the idea and applicability of the approximate method

Data arriving in time order (a data stream) arises in fields including physics, finance, medicine, and music, to name a few. Often the data comes from sensors (in physics and medicine for example) whose data rates continue to improve dramatically as sensor technology improves. Further, the number of sensors is increasing, so correlating data between sensors becomes ever more critical in order to distill knowlege from the data. In many applications such as finance, recent correlations are of far more interest than long-term correlation, so correlation over sliding windows (windowed correlation) is the desired operation. Fast response is desirable in many applications (e.g., to aim a telescope at an activity of interest or to perform a stock trade). These three factors -- data size, windowed correlation, and fast response -- motivate this work.Previous work [10, 14] showed how to compute Pearson correlation using Fast Fourier Transforms and Wavelet transforms, but such techniques don't work for time series in which the energy is spread over many frequency components, thus resembling white noise. For such "uncooperative" time series, this paper shows how to combine several simple techniques -- sketches (random projections), convolution, structured random vectors, grid structures, and combinatorial design -- to achieve high performance windowed Pearson correlation over a variety of data sets.

We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: insertion of leaves and internal nodes,deletion of leaves,deletion of internal nodes with only one child,determining the least common ancestor of any two nodes. We also generalize the Dietz--Sleator "cup-filling" scheduling methodology, which may be of independent interest.

This paper considers various flavors of the following online problem: preprocess a text or collection of strings, so that given a query string p, all matches of p with the text can be reported quickly. In this paper we consider matches in which a bounded number of mismatches are allowed, or in which a bounded number of "don't care" characters are allowed. The specific problems we look at are: indexing, in which there is a single text t, and we seek locations where p matches a substring of t; dictionary queries, in which a collection of strings is given upfront, and we seek those strings which match p in their entirety; and dictionary matching, in which a collection of strings is given upfront, and we seek those substrings of a (long) p which match an original string in its entirety. These are all instances of an all-to-all matching problem, for which we provide a single solution.The performance bounds all have a similar character. For example, for the indexing problem with n=|t| and m=|p|, the query time for k substitutions is O(m + (c1 log n)k⁄k! + # matches), with a data structure of size O(n (c2 log n)k⁄k!) and a preprocessing time of O(n (c2 log n)k⁄k!), where c1,c2 > 1 are constants. The deterministic preprocessing assumes a weakly nonuniform RAM model; this assumption is not needed if randomization is used in the preprocessing.

We study economic incentives for influencing selfish behavior in networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. The quality of a routing of traffic is historically measured by the sum of all travel times, also called the total latency.It is well known that the outcome of selfish routing (a Nash equilibrium) does not minimize the total latency and can be improved upon with coordination, and that marginal cost pricing---charging each network user for the congestion effects caused by its presence---eliminates the inefficiency of selfish routing. However, the principle of marginal cost pricing assumes that (possibly very large) taxes cause no disutility to network users; this is appropriate only when collected taxes can be feasibly returned (directly or indirectly) to the users, for example via a lump-sum refund. If this assumption does not hold and we wish to minimize the total user disutility (latency plus taxes paid)---the total cost---how should we price the network edges? Intuition may suggest that taxes should never be able to improve the cost of a Nash equilibrium, but the famous Braess's Paradox shows this intuition to be incorrect.We consider strategies for pricing network edges to reduce the cost of a Nash equilibrium. Since levying a sufficiently large tax on an edge effectively removes it from the network, our study generalizes previous work on network design citend_hard. In this paper, we prove the following results.

We study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. The quality of a routing of traffic is measured by the sum of travel times (the total latency).It is well known that the outcome of selfish routing (a Nash equilibrium) does not minimize the total latency. An ancient strategy for improving the selfish solution is the principle of marginal cost pricing, which asserts that on each edge of the network, each network user on the edge should pay a tax offsetting the congestion effects caused by its presence. By pricing network edges according to this principle, the inefficiency of selfish routing can always be eradicated.This result, while fundamental, assumes a very strong homogeneity property: all network users are assumed to trade off time and money in an identical way. The guarantee also ignores both the algorithmic aspects of edge pricing and the unfortunate possibility that an efficient routing of traffic might only be achieved with exorbitant taxes. Motivated by these shortcomings, we extend this classical work on edge pricing in several different directions and prove the following results.We prove that the edges of a single-commodity network can always be priced so that an optimal routing of traffic arises as a Nash equilibrium, even for very general heterogeneous populations of network users.When there are only finitely many different types of network users and all edge latency functions are convex, we show how to compute such edge prices efficiently.We prove that an easy-to-check mathematical condition on the population of heterogeneous network users is both necessary and sufficient for the existence of edge prices that induce an optimal routing while requiring only moderate taxes.

Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C3 n log n+m). This algorithm is based on an efficient construction of tree packings which generalizes Edmonds' Theorem. These packings also yield a characterization of all minimal Steiner cuts of size C from which an efficient data structure for maintaining edge connectivity between vertices in S under edge insertion can be obtained. This data structure enables the efficient construction of a cactus tree for representing significant C-cuts among these vertices, called C-separations, in the same time bound. In turn, we use the cactus tree to give a fast implementation of an approximation algorithm for the Survivable Network Design problem due to Williamson, Goemans, Mihail and Vazirani.

In this paper, we show an O(n+m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O(nlog 2 m +m) time deterministic algorithm and an O(n log n+m) time Monte Carlo algorithm for the tree pattern matching problem.

We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for two-dimensional arrays. These trees also have the property that the node degrees may be large. We add a new back-propagation component to McCreight's algorithm and also give a high probability hashing scheme for large degrees. We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.

(MATH) This paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length m

We give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. The first algorithm, which is quite simple, runs in time $O(\frac{nk^3}{m}+n+m)$ on all patterns except k-break periodic strings (defined later). The second algorithm runs in time $O(\frac{nk^4}{m}+n+m)$ on k-break periodic patterns. The two classes of patterns are easily distinguished in O(m)time.

We consider suffix tree construction for situations with missing suffix links.Two examples of such situations are suffix trees for parameterized strings and suffix trees for 2D arrays.These trees also have the property that the node degrees may be large.We add a new back-propagation component to McCreight's algorithm and also give a high probability perfect hashing scheme to cope with large degrees.We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability.This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.

The following result is shown: On an n-node splay tree, the amortized cost of an access at distance d from the preceding access is O(log (d+1)). In addition, there is an O(n) initialization cost. The accesses include searches, insertions, and deletions.

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions of the two trees restricted to these items are isomorphic. We consider the case which occurs frequently in practice, i.e., the case when the trees are binary, and give an O(nlog n) time algorithm for this problem.

A special case of the dynamic finger conjecture is proved; this special case introduces a number of useful techniques.

In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

Article Free Access Share on Tree pattern matching and subset matching in randomized O(nlog3m) time Authors: Richard Cole Courant Institute, New York University Courant Institute, New York UniversityView Profile , Ramesh Hariharan Indian Institute of Science, Bangalore Indian Institute of Science, BangaloreView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 66–75https://doi.org/10.1145/258533.258553Published:04 May 1997Publication History 18citation510DownloadsMetricsTotal Citations18Total Downloads510Last 12 Months39Last 6 weeks8 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

This paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form of n + O(n/m) character comparisons, following preprocessing. Specifically, we show an upper bound of $n + \frac{8}{3(m+1)}(n-m)$ character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total and requires O(m) space and O(m2) time for preprocessing. The current best lower bound for online algorithms is $n + \frac{16}{7m+27}(n-m)$ character comparisons for $m=16k+19$, for any integer $k\geq 1$, and for general algorithms is $n+\frac{2}{m+3}(n-m)$ character comparisons, for $m=2k+1$, for any integer $k\geq 1$.

In this paper we study the ability of array-based networks to tolerate worst-case faults. We show that an $N \times N$ two-dimensional array can sustain $N^{1-\epsilon}$ worst-case faults, for any fixed $\epsilon > 0$, and still emulate T steps of a fully functioning $N \times N$ array in $O(T+N)$ steps, i.e., with only constant slowdown. Previously, it was known only that an array could tolerate a constant number of faults with constant slowdown. We also show that iffaulty nodes are allowed to communicate, but not compute, then an N-node one-dimensional array can tolerate $\log^k N$ worst-case faults, for any constant $k > 0$, and still emulate a fault-free array with constant slowdown, and this bound is tight.

We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2 log n off the best previous running time for a linear-work algorithm. The novelty in our approach is to divide the computation into two phases, the first of which finds only a partial solution. This idea has been used previously in parallel connected components algorithms. 1 Introduction We describe the first work-optimal minimum spanning forest (MSF) algorithm that runs in O(log n) time. The algorithm uses a random-sampling technique previously used by Karger, Klein, and Tarjan in a sequential linear-time algorithm and by Cole, Klein, and Tarjan in a parallel algorithm. These previous algorithms have the following form. Choose a random subset of edges, and recursively calculate the MSF of the sample graph, the graph consisting of the chosen edges. Use the recursively calculated minimum spanning forest to identify edges ...

This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link, can support up to B virtual channels. We show that it is possible to route any set of messages with L flits each, whose paths have congestion C and dilation D in O((L+ D) C(D log D) B B) flit steps, where a flit step is the time taken to transmit B flits, i.e., one flit per virtual channel, across a physical channel. We also prove a nearly matching lower bound; i.e., for any values of C, D, B, and L, where C, D B+1 and L=(1+0(1)) D, we show how to construct a network and a set of L-flit messages whose paths have congestion C and dilation D that require 0(LCD B B) flit steps to route. These upper and lower bounds imply that increasing the buffering capacity and the bandwidth of each physical channel by a factor of B can speed up a wormhole routing algorithm by a superlinear factor, i.e., a factor significantly larger than B. We also present a simple randomized wormhole routing algorithm for the butterfly network. The algorithm routes any q-relation on the inputs and outputs doi:10.1006 jcss.2000.1701, available online at http: www.idealibrary.com on

We show that even if every node or edge in an N-node butterfly network fails independently with some constant probability, p, it is still possible to identify a set of /spl Theta/(N) nodes between which packets can be routed in any permutation in O(logN) steps, with high probability. Although the analysis as complicated, the routing algorithm itself is relatively simple.

This paper studies the implicit costs of synchronization and the possible gains arising from avoiding synchronization in asynchronous environments. An asynchronous generalization of the PRAM model called the APRAM model is used and appropriate complexity measures are defined. The advantage that asynchrony provides is illustrated by analyzing two algorithms: a parallel summation algorithm which proceeds along an implicit complete binary tree and a recursive doubling algorithm which proceeds along a linked list.

This paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms, a lower bound of about $(1 + \frac{9}{4(m + 1)}) \cdot n$ character comparisons is obtained. For general algorithms, a lower bound of about $(1 + \frac{2}{m + 3}) \cdot n$ character comparisons is obtained. These lower bounds complement an on-line upper bound of about $(1 + \frac{8}{3(m + 1)}) \cdot n$ comparisons obtained recently by Cole and Hariharan. The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.

Given m points in the plane and a threshold t, a curve is defined to be robust if at least t points lie on it. Efficient algorithms for detecting robust curves are given; the key contribution is to use randomized sampling. In addition, an approximate version of the problem is introduced. A geometric solution to this problem is given; it too can be enhanced by randomization. These algorithms are readily generalized to solve the problem of robust curve detection in a scene of curve fragments: given a set of curve segments, a curve σ is defined to be robust if curve segments of total length at least l lie on σ. Again, both an exact and an approximate version of the problem are considered. The problems and solutions are closely related to the well-investigated Hough transform technique.

The problem of finding all occurrences of a pattern of length m in a text of length n is considered. It is shown that the Boyer–Moore string matching algorithm performs roughly $3n$ comparisons and that this bound is tight up to $O({n / m})$; more precisely, an upper bound of ${{3n - 3(n - m + 1)} / {(m + 2)}}$ comparisons is shown, as is a lower bound of $3n(1 - o(1))$ comparisons, as $\frac{n}{m} \to \infty $ and $m \to \infty $. While the upper bound is somewhat involved, its main elements provide a simple proof of a $4n$ upper bound for the same algorithm.

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching.>

In this paper we study the ability of array-based networks to tolerate faults.We show that an N x N twodimensional array can sustain N1 -' worst-case faults, for any fixed c >0, and still emulate a fully functioning N x N array with only constant slowdown.We also observe that even if every node fails with some fixed probability, p, with high probability the array can still emulate a fully functioning array with constant slowdown.Previously, no connected bounded-degree network was known to be able to tolerate constantprobability node failures without suffering more than a constant-factor loss in performance.Finally, we observe that if faulty nodes are allowed to communicate, but not compute, then an N-node one-dimensional array can tolerate logO(lJ N worst-case faults and still emulate a fault-free array with constant slowdown, and this bound is tight. 1

Previous article Correction: Parallel Merge SortRichard ColeRichard Colehttps://doi.org/10.1137/0222081PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Correction: Parallel Merge Sort." SIAM Journal on Computing, 22(6), p. 1349[1] Richard Cole, Parallel merge sort, SIAM J. Comput., 17 (1988), 770–785 10.1137/0217049 89m:68015 0651.68077 LinkISIGoogle Scholar[2] S. Saxena, , P. C. P. Bhatt and , V. C. Prasad, Time optimal parallel prefix algorithm, Unpublished manuscript Google Scholar Previous article FiguresRelatedReferencesCited byDetails Near Optimal Parallel Algorithms for Dynamic DFS in Undirected GraphsACM Transactions on Parallel Computing, Vol. 6, No. 3 Cross Ref Parallel Reachability in Almost Linear Work and Square Root Depth Cross Ref Skyline Queries with Noisy Comparisons20 May 2015 Cross Ref Database Management System on Flosolver Mk326 March 2015 | IETE Technical Review, Vol. 15, No. 6 Cross Ref Volume 22, Issue 6| 1993SIAM Journal on Computing History Submitted:02 April 1993Accepted:12 April 1993Published online:31 July 2006 InformationCopyright © 1993 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0222081Article page range:pp. 1349-1349ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

The paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form n + O(n/m) character comparisons, following preprocessing. Specifically, the authors show an upper bound of n+8/3(m+1)(n-m) character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total, requires O(m) space and O(m/sup 2/) time for preprocessing. In addition the following lower bounds are shown: for online algorithms, a bound of n+11/5(m+1) (n-m) character comparisons for m = 10 + 11 k, for any integer k >or= 1, and for general algorithms, a bound of n+2(n-m)/m+3 character comparisons, for m=2 k+l, for any integer k>or=1.>

We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. For general segments, we give an algorithm requiring optimal O(A + n log n) expected work and optimal O(logn) time, where A is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal O(n) expected work and O(logn log log n log n) expected time a , and a simpler algorithm requiring O(n log n) expected work. The serial algorithm corresponding to the latter is among the simplest known algorithms requiring O(n log n) expected operations. For a set of segments forming K chains, we give an algorithm requiring O(A + n log n + K log n) expected work and O(logn log log n log n) expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every log n steps. Keywords: randomized, parallel, trapez...

Part I of this paper presented a novel technique for approximate parallel scheduling and a new logarithmic time optimal parallel algorithm for the list ranking problem. In this part, we give a new logarithmic time parallel (PRAM) algorithm for computing the connected components of undirected graphs which uses this scheduling technique. The connectivity algorithm is optimal unless m = o(n log∗ n) in graphs of n vertices and m edges. (log(k) denotes the kth iterate of the log function and log∗ n denotes the least i such that log(i) n ≤ 2). Using known results, this new algorithm implies logarithmic time optimal parallel algorithms for a number of other graph problems, including biconnectivity, Euler tours, strong orientation and st-numbering. Another contribution of the present paper is a parallel union/find algorithm.

The technique of speeding up access into search structures by maintaining fingers that point to various locations of the search structure is considered. The problem of choosing, in a large search structure, locations at which to maintain fingers is treated. In particular, a server problem in which k servers move along a line segment of length m, where m is the number of keys in the search structure, is addressed. Since fingers may be arbitrarily copied, a server is allowed to jump, or fork, to a location currently occupied by another server. Online algorithms are presented and their competitiveness analyzed. It is shown that the case in which k=2 behaves differently from the case in which k>or=3, by showing that there is a four-competitive algorithm for k=2 that never forks its fingers. For k>or=3, it is shown that any online algorithm that does not fork its fingers can be at most Omega (m/sup 1/2/)-competitive. The main result is that for k=3 there is an online algorithm that forks and is constant competitive (independent of m, the size of the search structure). The algorithm is simple and implementable.>

This paper expands on the APRAM model introduced in [CZ89].It introduces a model under which processes may proceed at different and varying speeds.Using this model the implicit costs of synchronization can be studied.The merit of the model is exhibited by analyzing two key algorithms, parallel summation along an implicit binary tree and recursive doubling, and demonstrating that both asynchronous algorithms perform better then their synchronous counterparts in asynchronous settings.

The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree isInwhere the jth access is to the ij th item in symmetric order (the i0th item is the item originally at the root of the tree).In other words, the amortized cost of an access is 0(1 + log d), where the current access is at distance d from the previous access (distance being measured in terms of the number of items straddled by the two successive accesses); in addition, there is an additive O(n) initialization cost.In this paper, the following bound is shown:So instead of an O(n) initialization cost, an O(n log log n) initialization cost is demonstrated.Due to lack of space, in this extended abstract only some elements of the proof are shown.A complete proof outline is not given.

Article Free Access Share on The APRAM: incorporating asynchrony into the PRAM model Authors: R. Cole Courant Institute, New York University, LIENS, Ecole Normale Supérieure Courant Institute, New York University, LIENS, Ecole Normale SupérieureView Profile , O. Zajicek Courant Institute, New York University, LIENS, Ecole Normale Supérieure Courant Institute, New York University, LIENS, Ecole Normale SupérieureView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 169–178https://doi.org/10.1145/72935.72954Published:01 March 1989Publication History 74citation530DownloadsMetricsTotal Citations74Total Downloads530Last 12 Months36Last 6 weeks14 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 parallel algorithm for the prefix sums problem which runs in timeO( logn/log logn) usingnlog logn/lognprocessors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs inO(logn) time usingn/lognprocessors (optimal speedup).

In this paper we study several problems concerning the visibility of a polyhedral terrain σ from a point (or several points) lying above it. Our results are: (1) For a fixed point a, one can preproeess a in time O(nα(n) log n), to produce a data structure of size O(nα(n) log n), which supports fast ray shooting queries, where each such query asks for the point on σ that is visible from a in a specified direction. Here n is the number of faces of σ and α(n) is the extremely slowly growing functional inverse of Ackermann's function. (2) If the viewing point a can vary along a fixed vertical line L, then the entire visibility structure of σ from L is of combinatorial complexity O(nλ4(n)), where λ4(n) is the maximal length of an (n, 4) Davenport-Sehinzel sequence, and is nearly linear in n, and where the visibility structure in question is the decomposition of L x S2 into maximal connected regions, such that for each such region R, all points (a, u)∈ R are such that the ray from a ∈ L in direction u ∈ S2 first intersects σ at a point on the same face of σ. Furthermore, we present an O(nλ4(n)log n)-time algorithm that preprocesses L and σ into a data-structure of size O(nλ4(n)) which supports O(log2n) time ray shooting queries. (3) Concerning the results in (2) we show that (i) if L is not vertical, then the resulting visibility structure can be of size Ω(n3); (ii) there exist a vertical line L and a polyhedral terrain a with n faces, for which the resulting visibility structure is of size Ω(n2α(n)). (4) Finally, we consider the problem of placing on the surface σ one or several viewing points which collectively cover the entire surface (i.e. each point on σ is visible from at least one of these viewing “stations”). We show (i) in the case of a single viewing station, one can determine in time O(n log n) whether such a station exists, and if so, produce such a point; (ii) the problem of finding the smallest number of points on σ that can collectively see the entire surface σ is NP-hard.

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in $O(\log n)$ time with either a linear or a sublinear number of processors in the CREW PRAM model.

Given n points in the plane and an integer k, the problem of selecting that pair of points that determines the line with the kth smallest or largest slope is considered. In the restricted case, where k is $O(n)$, line sweeping gives an optimal, $O(n\log n)$-time algorithm. For general k the parametric search technique of Megiddo is used to describe an $O(n(\log n)^2 )$-time algorithm. This is modified to produce a new, optimal $O(n\log n)$-time selection algorithm by incorporating an approximation idea.

In this paper we give parallel algorithms for a number of problems defined on polygons and point sets. All of our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. In addition, our algorithms provide parallel analogues to well known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently that point-set problems, and that one can solve nearest-neighbor problems without explicitly constructing a Voronoi diagram.

We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log∗n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log∗/log log n) time.

This work describes a large number of constructions for sortingNintegers in the range [0,M- 1], forN≤M≤N2, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for allMand almost all running timesT. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.

We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and $O(\log n)$ time; the constant in the running time is small. We also give a more complex version of the algorithm for the EREW PRAM; it also uses n processors and $O(\log n)$ time. The constant in the running time is still moderate, though not as small.

We define a novel scheduling problem; it is solved in parallel by repeated, rapid, approximate reschedulings. This leads to the first optimal logarithmic time PRAM algorithm for list ranking. Companion papers show how to apply these results to obtain improved PRAM upper bounds for a variety of problems on graphs, including the following: connectivity, biconnectivity, Euler tour and $st$-numbering, and a number of problems on trees.

We present techniques for parallel divide-and-conquer, resulting in improved parallel algorithms for a number of problems. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition (hence, polygon triangulation), and planar point location (hence, Voronoi diagram construction). We also give efficient parallel algorithms for fractional cascading, 3-dimensional maxima, 2-set dominance counting, and visibility from a point. All of our algorithms run in O(log n) time with either a linear or sub-linear number of processors in the CREW PRAM model.

Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of O (log n ) time (or more) for many applications of this technique.

For any set X of points (in any dimension) and any $k = 1,2, \cdots $, we introduce the concept of the k-hull of X. The k-hull is the set of points p such that for any hyperplane containing p there are at least k points of X in each closed half-space determined by the hyperplane. Several computational problems related to k-hulls are studied here, including computing the k-hull and finding a point in the k-hull. Some of our algorithms are of interest in themselves because of the techniques employed; in particular, a “parametric” searching technique is used in a nontrivial way.

Abstract We introduce a new type of partition called a parallel planes partition. We prove there exists a parallel planes partition of any set of n points in arbitrary dimension. This partition yields a data structure for the half-space retrieval problem in arbitrary dimension; it has linear size and achieves a sublinear query time. Also, we give efficient algorithms for computing this partition.

We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn) time; the constant in the running time is small. We also give a more complex version of the algorithm for the EREW PRAM; it also uses n processors and O(logn) time. The constant in the running time is still moderate, though not as small.

We study two parallel scheduling problems and their use in designing parallel algorithms. First, we define a novel scheduling problem; it is solved by repeated, rapid, approximate reschedulings. This leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time. Our second scheduling result is for computing prefix sums of logn bit numbers. We give an optimal parallel algorithm for the problem which runs in sublogarithmic time. These two scheduling results together lead to logarithmic time PRAM algorithms for the connectivity, biconnectivity and minimum spanning tree problems. The connectivity and biconnectivity algorithms are optimal unless m = o(nlog*n), in graphs of n vertices and m edges.

We present efficient algorithms for the following geometric problems: (i) Preprocessing of a 2-D polyhedral terrain so as to support fast ray shooting queries from a fixed point. (ii) Determining whether two disjoint interlocking simple polygons can be separated from one another by a sequence of translations. (iii) Determining whether a given convex polygon can be translated and rotated so as to fit into another given polygonal region. (iv) Motion planning for a convex polygon in the plane amidst polygonal barriers. All our algorithms make use of Davenport Schinzel sequences and on some generalizations of them; these sequences are a powerful combinatorial tool applicable in contexts which involve the calculation of the pointwise maximum or minimum of a collection of functions.

Article Free Access Share on Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms Authors: R Cole New York University and Tel Aviv University New York University and Tel Aviv UniversityView Profile , U Vishkin New York University and Tel Aviv University New York University and Tel Aviv UniversityView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 206–219https://doi.org/10.1145/12130.12151Online:01 November 1986Publication History 118citation925DownloadsMetricsTotal Citations118Total Downloads925Last 12 Months39Last 6 weeks11 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

This work comprises two parts: lower bounds and upper bounds in VLSI circuits. The upper bounds are for the sorting problem: we describe a large number of constructions for sorting N numbers in the range [0,M] for the standard VLSI bit model. Among other results, we attain: • VLSI sorter constructions that are within a constant factor of optimal size for almost all number ranges M (including M = N), and running times T. • A fundamentally new merging network for sorting numbers in a bit model. • New organizational approaches for optimal tuning of merging networks and the proper management of data flow. The lower bounds apply to a variety of problems. We present two new techniques for establishing lower bounds on the information flow in VLSI circuits. They are: • An averaging technique, which is easy to apply to a variety of problems, including a long standing question regarding the AT2 complexity for sorting. • A technique for constructing fooling sets in instances where our averaging method is unlikely to provide an adequate bound.

Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. We give a general method that trims a factor o f 0(logn) time (or more) for many applications of this technique.

A solution to the 'Detailed Routing given a Homotopy' (DRH) problem is given in O(n + mlogm + D(m)) operations. The solution uses n + mlogm homotopy queries that are elementary; they are answerable based solely on "local properties" of modules, terminals, and wire connections. In addition, we need O(m) more complex queries, which are represented in the D(m) term. These queries must account for the total number of crossin s occurringfor selected test segments.

For any set X of points (in any dimension) and any k = 1,2, ..., we introduce the concept of the k-hull of X. This unifies the well-known notion of 'convex hulls' with the notion of 'centers' recently introduced by F.F. Yao. The concept is intimately related to some other concepts (k-belts, k-sets) studied by Edelsbrunner, Welzl, Lovász, Erdös and others.

A large class of geometric retrieval problems has the following form. Given a set X of geometric objects, preprocess to obtain a data structure D(X). Now use D(X) to rapidly answer queries on X. We say an algorithm for such a problem has (worst-case) space-time complexity O(f(n),g(n)) if the space requirement for D(X) is O(f) and the 'locate run-time' required for each retrieval is O(g). We show three techniques which can consistently be exploited in solving such problems. For instance, using our techniques, we obtain an O(n2+e, lognlog(l/∈)) spacetime algorithm for the polygon retrieval problem, for arbitrarily small ∈, improving on the previous solution having complexity O(n7,logn).

The present paper shows how to find a minimal edge coloring of a bipartite graph with E edges and V vertices in time $O(E\log V)$.