9698255
Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.
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.
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
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.
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.
9220714
Extracting Context-Sensitive Models in Inductive Logic Programming
Given domain-specific background knowledge and data in the form of examples, an Inductive Logic Programming (ILP) system extracts models in the data-analytic sense. We view the model-selection step facing an ILP system as a decision problem, the solution of which requires knowledge of the context in which the model is to be deployed. In this paper, "context" will be defined by the current specification of the prior class distribution and the client's preferences concerning errors of classification. Within this restricted setting, we consider the use of an ILP system in situations where: (a) contexts can change regularly. This can arise for example, from changes to class distributions or misclassification costs; and (b) the data are from observational studies. That is, they may not have been collected with any particular context in mind. Some repercussions of these are: (a) any one model may not be the optimal choice forall contexts; and (b) not all the background information provided may be relevant for all contexts. Using results from the analysis of Receiver Operating Characteristic curves, we investigate a technique that can equip an ILP system to reject those models that cannot possibly be optimal in any context. We present empirical results from using the technique to analyse two datasets concerned with the toxicity of chemicals (in particular, their mutagenic and carcinogenic properties). Clients can, and typically do, approach such datasets with quite different requirements. For example, a synthetic chemist would require models with a low rate of commission errors which could be used to direct efficiently the synthesis of new compounds. A toxicologist on the other hand, would prefer models with a low rate of omission errors. This would enable a more complete identification of toxic chemicals at a calculated cost of misidentification of non-toxic cases as toxic. The approach adopted here attempts to obtain a solution that contains models that are optimal for each such user according to the cost function that he or she wishes to apply. In doing so, it also provides one solution to the problem of how the relevance of background predicates is to be assessed in ILP.
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.
15971402
Pfair scheduling: beyond periodic task systems
We consider variants of Pfair and ER-fair scheduling in which subtasks may be released late, i.e., there may be separation between consecutive windows of the same task. We call such tasks intra-sporadic tasks. There are two main contributions. First, we show the existence of a Pfair (and hence ER-fair) schedule for any intra-sporadic task system whose utilization is at most the number of available processors. Second, we give a polynomial-time algorithm that is optimal for scheduling intra-sporadic tasks in a Pfair or ER-fair manner on systems of one or two processors.
18104124
A Note on Two Simple Transformations for Improving the Efficiency of an ILP System
Inductive Logic Programming (ILP) systems have had noteworthy successes in extracting comprehensible and accurate models for data drawn from a number of scientific and engineering domains. These results suggest that ILP methods could enhance the model-construction capabilities of software tools being developed for the emerging discipline of "knowledge discovery from databases." One significant concern in the use of ILP for this purpose is that of efficiency. The performance of modern ILP systems is principally affected by two issues: (1) they often have to search through very large numbers of possible rules (usually in the form of definite clauses); (2) they have to score each rule on the data (usually in the form of ground facts) to estimate "goodness". Stochastic and greedy approaches have been proposed to alleviate the complexity arising from each of these issues. While these techniques can result in order-of-magnitude improvements in the worst-case search complexity of an ILP system, they do so at the expense of exactness. As this may be unacceptable in some situations, we examine two methods that result in admissible transformations of clauses examined in a search. While the methods do not alter the size ofthe search space (that is, the number of clauses examined), they can alleviate the theorem-proving effort required to estimate goodness. The first transformation simply involves eliminating literals using a weak test for redundancy. The second involves partitioning the set of literals within a clause into groups that can be executed independently of each other. The efficacy ofthe se transformations are evaluated empirically on a number of well-known ILP datasets. The results suggest that for problems that require the use of highly nondeterminate predicates, the transformations can provide significant gains as the complexity of clauses sought increases.
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.