10183251
Approximating low-congestion routing and column-restricted packing problems
Abstract We contribute to a body of research asserting that the fractional and integral optima of column-sparse integer programs are “nearby”. This yields improved approximation algorithms for some generalizations of the knapsack problem, with applications to low-congestion routing in networks, file replication in distributed databases, and other packing problems.
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.
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.
8868988
Contention resolution with constant expected delay
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expected delay (time to get serviced) of every message is O(log n) when messages are generated according to a Bernoulli distribution with generation rate up to about 1/10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than 1/e, and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to 1/e. (Each message constitutes a new user.)
To achieve (a), we first show how to simulate (b) using n synchronized users, and then show how to build the synchronization into the protocol.
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
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.
9141341
Dependent rounding and its applications to approximation algorithms
We 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 improved (approximation) algorithms for various problems. These include:---low congestion multi-path routing;---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, as well as (iii) capacitated vertex cover; and---fair scheduling of jobs on unrelated parallel machines.
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
6168494
Approximation algorithms for scheduling on multiple machines
We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming, quadratic programming, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. We obtain the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria (3/2 and 2, respectively); (ii) better-than-two approximation guarantees for scheduling under the L/sub p/ norm for all 1 < p < /spl infin/, improving on the 2-approximation algorithms of Azar & Epstein; and (iii) the first constant-factor multicriteria approximation algorithms that handle the weighted completion-time and any given collection of integer L/sub p/ norms. Our algorithm yields a common generalization of rounding theorems due to Karp et al and Shmoys & Tardos; among other applications, this yields an improved approximation for scheduling with resource-dependent processing times studied by Grigoriev et al.
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.
16475170
Optimal rate-based scheduling on multiprocessors
The PD2 Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD2 is also optimal for scheduling "rate-based" tasks whose processing steps may be highly jittered. The rate-based task model we consider generalizes the widely-studied sporadic task model.