We consider the problem of maximizing the number of jobs completed by their deadline in an online single processor system where the jobs are preemptable and have release times. So in the standard three field schedulin...
详细信息
We consider the problem of maximizing the number of jobs completed by their deadline in an online single processor system where the jobs are preemptable and have release times. So in the standard three field scheduling notation, this is the online version of the problem 1 \r(i);pmtn\ Sigma(1 - U-i). We present a deterministic algorithm Lax, and show that for every instance I, it is the case that either Lax, or the well-known deterministic algorithm SRPT (Shortest Remaining Processing Time), is constant competitive on T. An immediate consequence of this result is a constant competitive randomized algorithm for this problem. It is known that no constant competitive deterministic algorithm exists for this problem. (C) 2003 Elsevier Inc. All rights reserved.
We propose an approach for analyzing the average performance of a given (randomized) local search algorithm, for a constraint satisfaction problem. Our approach consists of two approximations. Using a randomized algor...
详细信息
ISBN:
(纸本)3540201033
We propose an approach for analyzing the average performance of a given (randomized) local search algorithm, for a constraint satisfaction problem. Our approach consists of two approximations. Using a randomized algorithm for LDPCC decoding, we experimentally investigate the reliability of these approximations and show that they could be used as a tool for analyzing the average performance of randomized local search algorithms.
This article deals with randomized allocation processes placing sequentially n balls into n bins. We consider multiple-choice algorithms that choose d locations (bins) for each ball at random, inspect the content of t...
详细信息
This article deals with randomized allocation processes placing sequentially n balls into n bins. We consider multiple-choice algorithms that choose d locations (bins) for each ball at random, inspect the content of these locations, and then place the ball into one of them, for example, in a location with minimum number of balls. The goal is to achieve a good load balancing. This objective is measured in terms of the maximum load, that is, the maximum number of balls in the same bin. Multiple-choice algorithms have been studied extensively in the past. Previous analyses typically assume that the d locations for each ball are drawn uniformly and independently from the set of all bins. We investigate whether a nonuniform or dependent selection of the d locations of a ball may lead to a better load balancing. Three types of selection, resulting in three classes of algorithms, are distinguished: (1) uniform and independent, (2) nonuniform and independent, and (3) nonuniform and dependent. Our first result shows that the well-studied uniform greedy algorithm (class 1) does not obtain the smallest possible maximum load. In particular, we introduce a nonuniform algorithm (class 2) that obtains a better load balancing. Surprisingly, this algorithm uses an unfair tie-breaking mechanism, called Always-Go-Left, resulting in an asymmetric assignment of the balls to the bins. Our second result is a lower bound showing that a dependent allocation (class 3) cannot yield significant further improvement. Our upper and lower bounds on the maximum load are tight up to additive constants, proving that the Always-Go-Left algorithm achieves an almost optimal load balancing among all sequential multiple-choice algorithm. Furthermore, we show that the results for the Always-Go-Left algorithm can be generalized to allocation processes with more balls than bins and even to infinite processes in which balls are inserted and deleted by an oblivious adversary.
作者：
Bazzi, LMitter, SMIT
Dept Elect Engn & Comp Sci Informat & Decis Syst Lab Cambridge MA 02139 USA
Linear probabilistic divide-and-conquer recurrence relations arise when analyzing the running time of divide-and-conquer randomized algorithms. We consider first the problem of finding the expected value of the random...
详细信息
Linear probabilistic divide-and-conquer recurrence relations arise when analyzing the running time of divide-and-conquer randomized algorithms. We consider first the problem of finding the expected value of the random process T (x), described as the output of a randomized recursive algorithm T. On input x, T generates a sample (h(1),..., h(k)) from a given probability distribution on [0, 1](k) and recurses by returning g(x) + Sigma(i=1)(k) c(i)T(h(i)x) until a constant is returned when x becomes less than a given number. Under some minor assumptions on the problem parameters, we present a closed-form asymptotic solution of the expected value of T(x). We show that E[T(x)] = Theta(x(p) +x(p) integral(1)(x) (g(u)/u(p+1)) du), where p is the nonnegative unique solution of the equation Sigma(i=1)(k) c(i) E[h(i)(p)] = 1. This generalizes the result in [1] where we considered the deterministic version of the recurrence. Then, following [2], we argue that the solution holds under a broad class of perturbations including floors and ceilings that usually accompany the recurrences that arise when analyzing randomized divide-and-conquer algorithms.
We consider the problem of counting the number of contingency tables with given row and column sums. This problem is known to be #P-complete, even when there are only two rows (Random Structures algorithms 10(4) (1997...
详细信息
We consider the problem of counting the number of contingency tables with given row and column sums. This problem is known to be #P-complete, even when there are only two rows (Random Structures algorithms 10(4) (1997) 487). In this paper we present the first fully polynomial randomized approximation scheme for counting contingency tables when the number of rows is constant. A novel feature of our algorithm is that it is a hybrid of an exact counting technique with an approximation algorithm, giving two distinct phases. In the first, the columns are partitioned into "small" and "large". We show that the number of contingency tables can be expressed as the weighted sum of a polynomial number of new instances of the problem, where each instance consists of some new row sums and the original large column sums. In the second phase, we show how to approximately count contingency tables when all the column sums are large. In this case, we show that the solution lies in approximating the volume of a single convex body, a problem which is known to be solvable in polynomial time (J. ACM 38 (1) (1991) 1). (C) 2003 Elsevier Inc. All rights reserved.
The implementation of multidimensional systems in embedded devices is a major design challenge due to the high algorithmic complexity of the applications. The authors suggest a novel application-level synthesis method...
详细信息
The implementation of multidimensional systems in embedded devices is a major design challenge due to the high algorithmic complexity of the applications. The authors suggest a novel application-level synthesis methodology for those parts of the embedded application which are characterized by being Lebesgue measurable (the computation involved in signal and image processing systems is Lebesgue measurable). The synthesis methodology, based on perturbation analysis, supports the design of analog, digital, or mixed implementations at the very high level of the system design cycle. The outputs of the methodology are quantitative indications regarding the maximum performance loss tolerable by the subsystems composing the application. Such information, augmented with a stochastic description of the tolerated perturbations, can be related to lower synthesis levels and guide the designer toward the final implementation of the embedded device. The perturbation analysis is based on randomized algorithms for an effective evaluation of the performance loss of the computational flow once affected by behavioral perturbations and a Tabu-search-inspired optimizing algorithm for distributing the tolerable performance loss at the system output along the computational subsystems composing the possibly multidimensional processing.
We study the generalization of covering problems such as the set cover problem to partial covering problems. Here we only want to cover a given number k of elements rather than all elements. For instance, in the k-par...
详细信息
We study the generalization of covering problems such as the set cover problem to partial covering problems. Here we only want to cover a given number k of elements rather than all elements. For instance, in the k-partial (weighted) set cover problem, we wish to compute a minimum weight collection of sets that covers at least k elements. As a main result, we show that the k-partial set cover problem and its special cases like the k-partial vertex cover problem are all fixed parameter tractable (with parameter k). As a second example, we consider the minimum weight k-partial t-restricted cycle cover problem. (C) 2002 Elsevier Science B.V. All rights reserved.
The notion of nonmalleable cryptography, an extension of semantically secure cryptography, is defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible ...
详细信息
The notion of nonmalleable cryptography, an extension of semantically secure cryptography, is defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext so that the respective plaintexts are related. The same concept makes sense in the contexts of string commitment and zero-knowledge proofs of possession of knowledge. Nonmalleable schemes for each of these three problems are presented. The schemes do not assume a trusted center;a user need not know anything about the number or identity of other system users. Our cryptosystem is the first proven to be secure against a strong type of chosen ciphertext attack proposed by Rackoff and Simon, in which the attacker knows the ciphertext she wishes to break and can query the decryption oracle on any ciphertext other than the target.
Based on the results in [4], we have shown that the statement ''I'm onlyinterested in a subset F of all possible functions, so the precondition of the NFL theorems is notfulfilled" is true with a prob...
详细信息
Based on the results in [4], we have shown that the statement ''I'm onlyinterested in a subset F of all possible functions, so the precondition of the NFL theorems is notfulfilled" is true with a probability close to one (if F is chosen uniformly and y and X havereasonable cardinalities). Further, the statements "In my application domain, functions with maximumnumber of local minima are not realistic" and "For some components, the objective functions underconsideration will not have the maximal possible steepness" lead to scenarios where the preconditionof the NFL theorem is not fulfilled. The fact that the precondition of the NFL theorem is violateddoes not say much about the performance of a particular algorithm averaged over the considered setof functions for a given performance measure. In particular, our results do not quantify anydifferences. That a problem class is not c.u.p. does not lead to a "free lunch", but ensures thepossibility of a "free appetizer", e.g., we know that there exists a performance measure wherealgorithms have different performance when averaged over all the considered objective functions.
We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution;the task is to determine parameter values that ...
详细信息
We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution;the task is to determine parameter values that lead to the given solution. We describe algorithms for solving such problems for minimum spanning trees, shortest paths, and other "optimal subgraph" problems and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.
暂无评论