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.
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>>
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.
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.
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.
17105049
Data-Driven Time-Parallelization in the AFM Simulation of Proteins
Molecular dynamics is a popular technique to simulate the behavior of physical systems, with resolution at the atomic scale. One of its limitations is that an enormous computational effort is required to simulate to realistic time spans. Conventional parallelization strategies have limited effectiveness in dealing with this difficulty. We recently introduced a more scalable approach to parallelization, where data from prior, related, simulations are used to parallelize a simulation in the time domain. We demonstrated its effectiveness in nano-mechanics simulations. In this paper, we develop our approach so that it can be used in a soft-matter application involving the atomic force microscopy simulation of proteins. We obtain an order of magnitude improvement in performance when we combine time parallelization with conventional parallelization. The significance of this work lies in demonstrating the promise of data-driven time parallelization in soft-matter applications, which are more challenging than the hard-matter applications considered earlier.
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.
12321308
Efficient gossip-based aggregate computation
Recently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE, and RANK of their values using O(n log log n) messages within O(log n log log n) rounds of communication. To the best of our knowledge, ours is the first result that shows how to compute these aggregates with high probability using only O(n log log n) messages. In contrast, the best known gossip-based algorithm for computing these aggregates requires O(nlog n) messages and O(log n) rounds. Thus, our algorithm allows system designers to trade off a small increase in round complexity with a significant reduction in message complexity. This can lead to dramatically lower network congestion and longer node lifetimes in wireless and sensor networks, where channel bandwidth and battery life are severely constrained.
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.
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.