1016131
An Improved Approximation Algorithm for Vertex Cover with Hard Capacities
In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph G = (V,E), the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. Previously, 2-approximation algorithms were developed with the assumption that multiple copies of a vertex may be chosen in the cover. If we are allowed to pick at most a given number of copies of each vertex, then the problem is significantly harder to solve. Chuzhoy and Naor (Proc. IEEE Symposium on Foundations of Computer Science, 481-489, 2002 ) have recently shown that the weighted version of this problem is at least as hard as set cover; they have also developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy-Naor bound of 3 and matching (up to lower-order terms) the best approximation ratio known for the vertex cover problem.
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.
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.
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
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.
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.
16380223
Learning Chomsky-like Grammars for Biological Sequence Families
This paper presents a new method of measuring performance when positives are rare and investigates whether Chomsky-like grammar representations are useful for learning accurate comprehensible predictors of members of biological sequence families. The positive-only learning framework of the Inductive Logic Programming (ILP) system CProgol is used to generate a grammar for recognising a class of proteins known as human neuropeptide precursors (NPPs). As far as these authors are aware, this is both the first biological grammar learnt using ILP and the first real-world scientific application of the positive-only learning framework of CProgol. Performance is measured using both predictive accuracy and a new cost function, em Relative Advantage (RA). The RA results show that searching for NPPs by using our best NPP predictor as a filter is more than 100 times more efficient than randomly selecting proteins for synthesis and testing them for biological activity. The highest RA was achieved by a model which includes grammar-derived features. This RA is significantly higher than the best RA achieved without the use of the grammar-derived features.
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.
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.
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.
11919636
Quick-release fair scheduling
In prior work on multiprocessor fairness, efficient techniques with provable properties for reallocating spare processing capacity have been elusive. In this paper, we address this shortcoming by proposing a new notion of multiprocessor fairness, called quick-release fair (QRfair) scheduling. Under QRfair scheduling, each task is specified by giving both a minimum and a maximum weight (i.e., processor share). The goal is to schedule each task (as the spare capacity changes) at a rate that is (i) at least that implied by its minimum weight and (ii) at most that implied by its maximum weight. We present a quick-release variant of the PD/sup 2/ Pfair scheduling algorithm called PD/sup Q/ and prove that the allocations of PD/sup Q/ always satisfy (i) and (ii). Also, we present results from simulation experiments that show the efficacy of PD/sup Q/.