8959226
Low-Discrepancy Sets For High-Dimensional Rectangles: A Survey
A sub-area of discrepancy theory that has received much attention in computer science recently, is that of explicit constructions of low-discrepancy point sets for various types of rectangle families in high dimension. This research has led to interesting applications in error-control coding, distributed protocols, Web document filtering, derandomization, and other areas. We give a short survey of this area here.
17073164
Improved approximations of packing and covering problems
Aravind Srinivasant Several important NP-hard combinatorial optimization problems can be posed as packing\couerirag integer pragramq the rarzrfomized rouradingtechnique of Raghavan & Thompson is a powerful tool to approximate them well. We present one elementary unifying property of all these integer programs (IPs), and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. Thk also yields a pessimistic estimator, thus presenting deter-ministic polynomial-time algorithms for them with approximation guarantees significantly better than those known.
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.
1554031
Chernoff-Hoeffding bounds for applications with limited independence
Chernoff-Hoeffding (CH) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v.'s). We present a simple technique that gives slightly better bounds than these and that more importantly requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. Additional methods are also presented, and the aggregate results are sharp and provide a better understanding of the proof techniques behind these bounds. These results also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. The limited independence result implies that a reduced amount and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the CH bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.
7189804
Low-Bandwidth Routing and Electrical Power Networks
Given a graph G and a (multi-)set of pairs of vertices in it, the classical NP-hard maximum edge-disjoint-paths problem (MDP) is to connect as many of the given pairs as possible using pairwise edge-disjoint paths in G. We study a relative of this problem: we have a network with fixed link capacities that may have to service large demands when necessary. In particular, individual demands are allowed to exceed capacities, and thus flows for some request pairs necessarily have to be split into different flow-paths. This is the framework for computational problems arising from: (i) electrical power networks due to the proposed deregulation of the electric utility industry in the USA, and (ii) applications such as real-time Internet services (e.g., telephone, fax, video). We show that these problems come in a few variants, some efficiently solvable and many NP-hard; we also present approximation algorithms for many of the NP-hard variants presented. Some of our approximation algorithms benefit from certain improved tail estimates that we derive; the latter also yield improved approximations for a family of packing integer programs.
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
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.
5564142
Provable algorithms for parallel generalized sweep scheduling
Abstract We present provably efficient parallel algorithms for sweep scheduling, which is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh from multiple directions. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Due to efficiency and coupling considerations, we have an additional constraint, namely, a mesh cell must be processed on the same processor along each direction. Problems similar in nature to sweep scheduling arise in several other applications, and here we formulate a combinatorial generalization of this problem that captures the sweep scheduling constraints,and call it the generalized sweep scheduling problem. Several heuristics have been proposed for this problem; see [S. Pautz, An algorithm for parallel S n sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)] and the references therein; but none of these have provable worst case performance guarantees. Here we present a simple, almost linear time randomized algorithm for the generalized sweep scheduling problem that (provably) gives a schedule of length at most O ( log 2 n ) times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length O ( log m log log log m ) times the optimal schedule for m processors. These are the first such provable guarantees for this problem. The algorithm can be extended with an additional multiplicative factor in the case when we have inter-processor communication latency, in the models of Rayward-Smith [UET scheduling with inter-processor communication delays, Discrete Appl. Math. 18 (1) (1987) 55–71] and Hwang et al. [Scheduling precedence graphs in systems with inter-processor communication times, SIAM J. Comput. 18(2) (1989) 244–257]. Our algorithms are extremely simple, and use no geometric information about the mesh; therefore, these techniques are likely to be applicable in more general settings. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice; combining this algorithm with a simple block decomposition also lowers the overall communication cost significantly. Finally, we perform a detailed experimental analysis of our algorithm. Our results indicate that the algorithm compares favorably with the length of the schedule produced by other natural and efficient parallel algorithms proposed in the literature [S. Pautz, An Algorithm for parallel S n sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)].
16314241
End-to-end packet-scheduling in wireless ad-hoc networks
Packet-scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model. The main focus of our work is the development of fully-distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. The packet-scheduling work by L eighton, Maggs and Rao (Combinatorica, 1994) and a basic distributed coloring procedure, originally due to Luby (J. Computer and System Sciences, 1993), underlie many of our algorithms. Experimental work of Finocchi, Panconesi, and Silvestri (SODA 2002) showed that a natural modification of Luby's algorithm leads to improved performance, and a rigorous explanation of this was left as an open question; we prove that the modified algorithm is provably better in the worst-case. Finally, using simulations, we study the impact of the routing strategy and the choice of parameters on the performance of our distributed algorithm for unit disk graphs.
1268789
Pharmacophore Discovery Using the Inductive Logic Programming System PROGOL
This paper presents a case study of a machine-aided knowledge discovery process within the general area of drug design. Within drug design, the particular problem of pharmacophore discovery is isolated, and the Inductive Logic Programming (ILP) system progol is applied to the problem of identifying potential pharmacophores for ACE inhibition. The case study reported in this paper supports four general lessons for machine learning and knowledge discovery, as well as more specific lessons for pharmacophore discovery, for Inductive Logic Programming, and for ACE inhibition. The general lessons for machine learning and knowledge discovery are as follows.1. An initial rediscovery step is a useful tool when approaching a new application domain.2. General machine learning heuristics may fail to match the details of an application domain, but it may be possible to successfully apply a heuristic-based algorithm in spite of the mismatch.3. A complete search for all plausible hypotheses can provide useful information to a user, although experimentation may be required to choose between competing hypotheses.4. A declarative knowledge representation facilitates the development and debugging of background knowledge in collaboration with a domain expert, as well as the communication of final results.
14106112
Mixed Pfair/ERfair scheduling of asynchronous periodic tasks
In this paper, we prove that a simplified variant of the PD Pfair algorithm, called PD/sup 2/, is optimal for scheduling any mix of early-release and non-early-release asynchronous tasks on a multiprocessor. This result breaks new ground by incorporating both early-release and non-early-release tasks under a common framework. In addition, all prior work on optimal multiprocessor Pfair scheduling algorithms has been limited to synchronous periodic task systems.