Nonpreemptive Coordination Mechanisms for Identical Machines

We focus on the problem of scheduling n weighted selfish tasks on m identical parallel machines and we study the performance of nonpreemptive coordination mechanisms. A nonpreemptive coordination mechanism consists of m local scheduling policies that decide the processing order of the tasks on each machine without delays or interruptions. We discuss the existence of Nash equilibria for this setting and show that it is not a guaranteed property of all nonpreemptive coordination mechanisms. Next, we focus on the wider class of randomized Nash equilibria and prove lower bounds on the price of anarchy. Our lower bounds are presented in comparison to the currently best known coordination mechanism (which uses delays) and lead to the conclusion that preemption or delays are required in order to improve on the currently best known solution.     

The complexity of updating snapshot objects

This paper proves Ω(m) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an m-component snapshot object from historyless objects. These lower bounds follow from lower bounds for a new, more general class of implementations from base objects of any type. This work extends a similar lower bound by Israeli and Shirazi for implementations of m-component single-writer snapshot objects from single-writer registers.     

A Hybridizable and Superconvergent Discontinuous Galerkin Method for Biharmonic Problems

In this paper, we introduce and analyze a new discontinuous Galerkin method for solving the biharmonic problem Δ² u=f. The method has two main, distinctive features, namely, it is amenable to an efficient implementation, and it displays new superconvergence properties. Indeed, although the method uses as separate unknowns u,? u,Δu and ?Δu, the only globally coupled degrees of freedom are those of the approximations to u and Δu on the faces of the elements. This is why we say it can be efficiently implemented. We also prove that, when polynomials of degree at most k≥1 are used on all the variables, approximations of optimal convergence rates are obtained for both u and ? u; the approximations to Δu and ?Δu converge with order k+1/2 and k?1/2, respectively. Moreover, both the approximation of u as well as its numerical trace superconverge in L ²-like norms, to suitably chosen projections of u with order k+2 for k≥2. This allows the element-by-element construction of another approximation to u converging with order k+2 for k≥2. For k=0, we show that the approximation to u converges with order one, up to a logarithmic factor. Numerical experiments are provided which confirm the sharpness of our theoretical estimates.     

The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity

The rth order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. This paper tightens the lower bounds of the second order nonlinearity of three classes of Boolean functions in the form f(x)=tr(x^d) in n variables, where (1) d=2^m+1+3 and n=2m, or (2) , n=2m and m is odd, or (3) d=2^2r+2^r+1+1 and n=4r.     

Time-Bounded Kolmogorov Complexity and Solovay Functions

A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c ₀ and all computable functions t such that c ₀ n??t(n), the time-bounded version K ^t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if ?? _g =??2^?g(n) is Martin-Löf random. We obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin??s ?? extends to the time-bounded case in so far as $\Omega _{ \textnormal{K}^{t}}$ is Martin-Löf random for any t as above. As a step in the direction of a characterization of K-triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is O(g(n)?K(n))-jump traceable for all computable Solovay functions g. Furthermore, this equivalence remains true when the universal quantification over all computable Solovay functions in the second statement is restricted either to all functions of the form K ^t for some function t as above or to a single function K ^t of this form. Finally, we investigate into the plain Kolmogorov complexity C and its time-bounded variant C ^t of initial segments of computably enumerable sets. Our main theorem here asserts that every high c.e. Turing degree contains a c.e. set B such that for any computable function t there is a constant c _t >0 such that for all m it holds that C ^t (B?m)??c _t ?m, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C ^t (A?m)??logm+c. By similar methods it can be shown that any high degree contains a set B such that C ^t (B?m)??⁺ m/4. The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes et al. (Theor. Comput. Sci. 132(1?C2):37?C70, 1994) that every high degree contains a strongly deep set.     

Compact DSOP and Partial DSOP Forms

Given a Boolean function f on n variables, a Disjoint Sum-of-Products (DSOP) of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals f, such that no two products cover the same minterm of f. DSOP forms are a special instance of partial DSOPs, i.e. the general case where a subset of minterms must be covered exactly once and the other minterms (typically corresponding to don’t care conditions of f) can be covered any number of times. We discuss finding DSOPs and partial DSOPs with a minimal number of products, a problem theoretically connected with various properties of Boolean functions and practically relevant in the synthesis of digital circuits. Finding an absolute minimum is hard, in fact we prove that the problem of absolute minimization of partial DSOPs is NP-hard. Therefore it is crucial to devise a polynomial time heuristic that compares favorably with the known minimization tools. To this end we develop a further piece of theory starting from the definition of the weight of a cube c as a functions of the number of fragments induced on other cubes by the selection of c, and show how cube weights can be exploited for building a class of minimization heuristics for DSOP and partial DSOP synthesis. A set of experiments conducted on major benchmark functions show that our method, with a family of variants, always generates better results than the ones of previous heuristics, including the method based on a BDD representation of f.     

Finding one of D defective elements in some group testing models

In contrast to the classical goal of group testing, we consider the problem of finding m defective elements out of D (m ?? D). We analyze two different test functions. We give adaptive strategies and present lower bounds for the number of tests and show that our strategy is optimal for m = 1.     

Minimizing total completion time for re-entrant flow shop scheduling problems

In this paper, we study re-entrant flow shop scheduling problems with the objective of minimizing total completion time. In a re-entrant scheduling problem, jobs may visit some machines more than once for processing. The problem is NP-hard even for machine number m=2. A heuristic algorithm is presented to solve the problem, in which an effective k-insertion technique is introduced as the improvement strategy in iterations. Computational experiments and analyses are performed to give guidelines of choosing parameters in the algorithm. We also provide a lower bound for the total completion time of the optimal solution when there are only two machines. Objective function values of the heuristic solutions are compared with the lower bounds to evaluate the efficiency of the algorithm. For randomly generated instances, the results show that the given heuristic algorithm generates solutions with total completion times within 1.2 times of the lower bounds in most of the cases.     

New upper and lower bounds for the eigenvalues of the Sturm-Liouville problem

We derive new inequalities for the eigenvaluesλ _k of the Sturm-Liouville problem?u″+qu=λu, u(0)=u(π)=0 under the usual hypothesis thatq has mean value zero. The estimates give upper and lower bounds of the form |λ _k ?k ²|≤p _1,m k ^?m +P _2,m k ^2m ,k ²≥3‖q‖ _m ,m=1, 2 where ‖q‖ _m is the norm ofq in a Sobolev spaceH ^m (0, π) and theP's are homogeneous polynomials of degree at most 3 in ‖q‖ _m . Such bounds are used in the analysis of the inverse Sturm-Liouville problem.     

On-line scheduling with extendable working time on a small number of machines

Speranza and Tuza [Ann. Oper. Res. 86 (1999) 494-506] studied the on-line problem of scheduling jobs on m identical machines with extendable working time. In this problem, each machine is assumed to have an identical regular working time, which can be extended if necessary. The working time of a machine is the larger one between its regular working time and the total processing time of jobs assigned to it. The objective is to minimize the total working time of machines. They presented an on-line algorithm H_x, with a competitive ratio at most 1.228 for any number of machines by choosing an appropriate parameter x. In this paper we consider a small number of machines. The best choices of x are given for m=2,3,4 and the tight bounds, 7/6, 11/9 and 19/16, respectively, are proved. Among them, the algorithm for m=2 is best possible. We then derive a new algorithm for m=3 with a competitive ratio 7/6.     

Dimension Extractors and Optimal Decompression

A dimension extractor is an algorithm designed to increase the effective dimension—i.e., the amount of computational randomness—of an infinite binary sequence, in order to turn a “partially random” sequence into a “more random” sequence. Extractors are exhibited for various effective dimensions, including constructive, computable, space-bounded, time-bounded, and finite-state dimension. Using similar techniques, the Ku?era-Gács theorem is examined from the perspective of decompression, by showing that every infinite sequence S is Turing reducible to a Martin-Löf random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S, which is shown to be the optimal ratio of query bits to computed bits achievable with Turing reductions. The extractors and decompressors that are developed lead directly to new characterizations of some effective dimensions in terms of optimal decompression by Turing reductions.     

Trimmed Moebius Inversion and Graphs of Bounded Degree

We study ways to expedite Yates’s algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family ? of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of U with k sets from ? in time within a polynomial factor (in n) of the number of supersets of the members of ?. Relying on an projection theorem of Chung et al. (J. Comb. Theory Ser. A 43:23–37, 1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs with maximum degree Δ. In particular, we show how to compute the domatic number in time within a polynomial factor of (2^Δ+1?2) ^n/(Δ+1) and the chromatic number in time within a polynomial factor of (2^Δ+1?Δ?1) ^n/(Δ+1). For any constant Δ, these bounds are O((2?ε) ⁿ ) for ε>0 independent of the number of vertices n.     

Generation of Random Digital Simple Curves with Artistic Emulation

This paper presents two novel interdependent techniques for random digital simple curve generation. The first one is about generating a curve of finite length, producing a sequence of points defining a digital path ρ ‘on the fly’. The second is for the creation of artistic sketches from line drawings and edge maps, using multiple instances of such random digital paths. A generated digital path ρ never intersects or touches itself, and hence becomes simple and irreducible. This is ensured by detecting every possible trap formed by the previously generated part of ρ, which, if entered into, cannot be exited without touching or intersecting ρ. The algorithm is completely free of any backtracking and its time complexity is linear in the length of ρ. For artistic emulation, a curve-constrained domain is defined by the Minkowski sum of the input drawing with a structuring element whose size varies with the pencil diameter. An artist’s usual trait of making irregular strokes and sub-strokes, with varying shades while sketching, is thus captured in a realistic manner. Algorithmic solutions of non-photorealism are perceived as an enrichment of contemporary digital art. Simulation results for the presented algorithms have been furnished to demonstrate their efficiency and elegance.     

Error bounds for complementarity problems with tridiagonal nonlinear functions

In this paper we consider the complementarity problem NCP(f) with f(x) = Mx + φ(x), where M ∈ R ^n×n is a real matrix and φ is a so-called tridiagonal (nonlinear) mapping. This problem occurs, for example, if certain classes of free boundary problems are discretized. We compute error bounds for approximations \({\hat x}\) to a solution x* of the discretized problems. The error bounds are improved by an iterative method and can be made arbitrarily small. The ideas are illustrated by numerical experiments.     

Online hierarchical scheduling: An approach using mathematical programming

This paper considers an online hierarchical scheduling problem on parallel identical machines. We are given a set of m machines and a sequence of jobs. Each machine has a different hierarchy, and each job also has a hierarchy associated with it. A job can be assigned to a machine only if its hierarchy is no less than that of the machine. The objective is to minimize the makespan, i.e., the maximum load of all machines. Two models are studied in the paper. For the fractional model, we present an improved algorithm and lower bounds. Both the algorithm and the lower bound are based on solutions of mathematical programming. For any given m, our algorithm is optimal by numerical calculation. For the integral model, we present both a general algorithm for any m, and an improved algorithm with better competitive ratios of 2.333 and 2.610 for m=4 and 5, respectively.     

Randomized Priority Queues for Fast Parallel Access

We present simple randomized algorithms for parallel priority queues on distributed memory machines. Inserting O(n) elements or deleting the O(n) out ofmsmallest elements usingnprocessors requires O(T_coll+ log(m/n)) amortized time with high probability whereT_collbounds the time for performing prefix sums and randomized routing. The memory requirement is bounded by (m/n)(1 +o(1)) + O(logn) whp. These bounds are an improvement over the best previously known algorithms for many interconnection networks and even matches the speed of the best known PRAM algorithms. Generalizations for accessing thek⪢nsmallest elements are even more efficient. A portable implementation using MPI demonstrates that our approach is already useful for medium scale parallelism. Two parallel selection algorithms for randomly placed data are a spin-off. One runs in time O(T_coll) with high probability, beating a lower bound for the worst case. The other requires only a single reduction operation.     

A Generalization of the Convex Kakeya Problem

Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya’s problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(nlogn)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.     

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

We consider the problems of learning the optimal action-value function and the optimal policy in discounted-reward Markov decision processes (MDPs). We prove new PAC bounds on the sample-complexity of two well-known model-based reinforcement learning (RL) algorithms in the presence of a generative model of the MDP: value iteration and policy iteration. The first result indicates that for an MDP with N state-action pairs and the discount factor γ∈[0,1) only O(Nlog(N/δ)/((1?γ)³ ε ²)) state-transition samples are required to find an ε-optimal estimation of the action-value function with the probability (w.p.) 1?δ. Further, we prove that, for small values of ε, an order of O(Nlog(N/δ)/((1?γ)³ ε ²)) samples is required to find an ε-optimal policy w.p. 1?δ. We also prove a matching lower bound of Θ(Nlog(N/δ)/((1?γ)³ ε ²)) on the sample complexity of estimating the optimal action-value function with ε accuracy. To the best of our knowledge, this is the first minimax result on the sample complexity of RL: the upper bounds match the lower bound in terms of N, ε, δ and 1/(1?γ) up to a constant factor. Also, both our lower bound and upper bound improve on the state-of-the-art in terms of their dependence on 1/(1?γ).