14399319
Improved distributed algorithms for coloring and network decomposition problems
This paper deals with the problems of computing a maximal independent set and a vertex coloring in a dktributed model of computation. Given a connected graph G = (V, E) with IVI = n and maximum degree A such that G is neither a complete graph nor an odd cycle, Brooks’ theorem shows that G can be colored with A colors. We generalize thk as follows: let G – w be A-colored; then, v can be colored by considering the vertices in an O(loga n) radius around v, and this is tight. Using this, we show that A-coloring G is reducible in 0(log3 n/log A) time to (A+ I)-vertex coloring G in a distributed model. This leads to fast distributed algorithms, and a linear–processor NC algorithm, for Acoloring. We also prove a tight Q(diameter(G)) lower bound for A-edge-coloring bipartite graphs, even with unlimited randomness. When A = 2, this implies an Q(n) lower bound for vertex coloring paths and even cycles. A fundamental notion in distributed graph algorithms is that of a cluster decomposition, introduced by Awerbuch, Goldberg, Luby and Plotkin. We improve the existing bounds by showing how to compute a cluster decomposition in O(n”(’(”)) ) time, where e(n) = 1/=. This implies improved bounds for several problems, such as computing a maximal independent set and a (A + I )-coloring. We also show how to compute a A–coloring within the same time bound, using our reduction technique. Next, we show that the problem of doing better than O(n”(’(m))) time for cluster decomposition is self-reducible to graphs of “intermediate” diameter and degree. This pinpoints the weak points of existing cluster decomposition algorithms. *This research was supported in part by NSF PYI award CGR89-96272 with matching support from UPS and Sun Microsystems. Permission to copy without fee ell or part of this material is granted provided that the copiss are not made or distributed for direct commercial advantage, the ACM copyright notica and tha title of the publication and its date appear, and notice ie given that copying is by permission of the Association for Computing Machinery. To copy otharwise, or to republish, requires a fee and/or specific permieaion. 24th ANNUAL ACM STOC 5/92/VICTORIA, B. C., CANADA a 1992 ACM 0-89791-51 2-7192 /000410!581 . ..$1.50
2418753
Computing with very weak random sources
For any fixed /spl epsiv/>0, we show how to simulate RP algorithms in time n/sup O(log n/) using the output of a /spl delta/-source with min-entropy R(/spl epsiv/). Such a weak random source is asked once for R(/spl epsiv/) bits; it outputs an R-bit string such that any string has probability at most 2/sup -R/(/spl epsiv//). If /spl epsiv/>1-1/(k+1), our BPP simulations take time n/sup O(log(k/ n)) (log/sup (k/) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R/sup /spl Omega/(1/), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson.<<ETX>>
23028632
Mechanism design for intellectual property rights protection
Estimates for the annual size of software piracy are in the region of $15 billion. The problem is also manifest in other forms of intellectual property. The explosive growth of the Internet and other communications networks has accentuated this problem. The new infrastructure has facilitated piracy by effectively reducing the cost of copying to negligible levels. (Recently, the FBI launched an operation called “Cyber Strike,” with the objective of curbing illegal copying and distribution of software over computer networks.) A naive suggestion has been that intellectual property rights (IPR) violation is actually beneficial from the social point of view, since it decreases the monopoly power of the provider. However, the flip side of this argument is that the IPR violations decrease the incentive for innovation because they lead to lower profits. In this paper, several mechanisms for IPR protection are designed. The mechanisms involve two tools: the level of enforcement (i.e., the probability that an IPR violator will be apprehended) and the penalty to be levied on an apprehended IPR violator. These tools are analyzed by considering the tradeoff between social welfare and the provider’s profit. The paper considers a provider who wants to maximize his profit and a policy maker who wants to maximize “net” social welfare (defined as welfare less any costs of enforcement), subject to a target profit for the provider. The consumers choose from among three options: buy, copy, or stay out of the market. A game-theoretic framework is adopted, where the policy maker, the provider, and the consumers get to move in that order. Among the results, the research shows that
2380498
Improved bounds and algorithms for hypergraph two-coloring
We show that for all large n, every n-uniform hypergraph with at most 0.7/spl radic/(n/lnn)/spl times/2/sup n/ edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC/sup 1/ versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n/sup 1/3-0(1)//spl times/2/sup n/ due to Beck (1978). We further generalize this to a "local" version, improving on one of the first applications of the Lovasz Local Lemma.
39527744
Efficient Algorithms for the Minimum Weighted Dominating Clique Problem on Permutation Graphs
Given a graph G=(V, E) with real weights assigned to its vertices, a clique of G that also dominates its vertex set V, is called a dominating clique (DC) of G. Given a permutation graph G with all its vertices having nonnegative weights, and its permutation representation, the problem addressed in this paper is that of finding any minimum weight DC of G. We improve the existing O(|V|2) algorithm for this problem to O(|V|log|V|). The space complexity of our algorithm is O(|V|). We also present a |V| processor, O(log|V|) time, O(|V|log|V|) space parallel EREW PRAM algorithm for this problem.
12370019
New algorithmic aspects of the Local Lemma with applications to routing and partitioning
The Lovasz local lemma (LLL)is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy and Reed)have led to constructive versions. However, these methods do not capture some classes of applications of the LLL. We make progress on this by providing algorithmic approaches to two families of applications of the LLL. The first provides constructive versions of certain applications of an extension of the LLL (modeling, e.g., hypergraph-partitioning and low-congestion routing problems); the second provides new algorithmic results on constructing disjoint paths in graphs. Our results can also be seen as constructive upper bounds on the integrality gap of certain packing problems. One common theme of our work is a "gradual rounding" approach.
5246711
Dependent rounding in bipartite graphs
We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.
83148
Latency tolerance through parallelization of time in scientific applications
Summary form only given. Distributed computing environments, such as the grid, promise enormous raw computational power, but involve high communication overheads. It is therefore considered that they are ideally suited for "embarrassingly parallel" applications, such as Monte Carlo, and for certain applications where the loosely-coupled nature of the science involved in the simulations leads to a coarse grained computation. In a typical application, this is not feasible. We discuss our solution strategy, based on scalable functional decomposition, which can be used to keep the computation coarse grained, even on a large number of processors. Such decomposition can be attempted through a variety of means. We discuss the use of time parallelization to achieve this. We demonstrate results with a model problem, and then discuss its implementation for an important problem in nanomaterials simulation. We also show that this technique can be extended to make it inherently fault-tolerant.
14860992
Scalable Time-Parallelization of Molecular Dynamics Simulations in Nano Mechanics
Molecular dynamics (MD) is an important atomistic simulation technique, with widespread use in computational chemistry, biology, and materials. An important limitation of MD is that the time step size is small, requiring a large number of iterations to simulate realistic time spans. Conventional parallelization is not very effective for this. We recently introduced a new approach to parallelization, where data from related prior simulations are used to parallelize a new computation along the time domain. In our prior work, the size of the physical system in the current simulation needed to be identical to that of the prior simulations. The significance of this paper lies in demonstrating a strategy that enables this approach to be used even when the physical systems differ in size. Furthermore, this method scaled up to almost 1000 processors with close to ideal speedup in one case, where conventional methods scale to only 2-3 processors
5149437
The case for fair multiprocessor scheduling
In this paper, we compare the PD/sup 2/ Pfair algorithm to the EDF-FF partitioning scheme, which uses "first fit" (FF) as a partitioning heuristic and the earliest-deadline-first (EDF) algorithm for per-processor scheduling. We present experimental results that show that PD/sup 2/ is competitive with, and in some cases outperforms, EDF-FF. These results suggest that Pfair scheduling is a viable alternative to partitioning. Furthermore, as discussed herein, Pfair scheduling provides many additional benefits, such as simple and efficient synchronization, temporal isolation, fault tolerance, and support for dynamic tasks.
38425944
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints
We present polylogarithmic approximations for the R|prec|Cmax and R|prec|∑jwjCj problems, when the precedence constraints are “treelike” – i.e., when the undirected graph underlying the precedences is a forest. We also obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment – this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion+dilation”, as in other job shop scheduling approaches. The first step in our algorithm for the R|prec|Cmax problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random delays technique of Leighton, Maggs and Rao to the case of trees. For the weighted completion time, we show a certain type of reduction to the makespan problem, which dovetails well with the lower bound we employ for the makespan problem. For the special case of chains, we show a dependent rounding technique which leads to improved bounds on the weighted completion time and new bicriteria bounds for the flow time.