Narrow Results

We propose a completely general, informed randomized dynamic load balancing method called random seeking (RS) suitable for parallel algorithms with characteristics found in many search algorithms used in artificial intelligence and operations research and many divide-and-conquer algorithms. In it, source processors randomly seek out sink processors for load balancing by flinging "probe" messages. These probes not only locate sinks, but also collect load distribution information which is used to efficiently regulate load balancing activities. We empirically compare RS with a well-known randomized dynamic load balancing method, the random communication (RC) strategy, by using them in parallel best-first branch-and-bound algorithms on up to 512 processors of a parallel system. We find that the RC execution times are more than those of RS by 16–67% when used to perform combined dynamic quantitative and qualitative load balancing, and by 9–74% when used to perform only dynamic quantitative load balancing.

The scheduling problem deals with the optimal assignment of a set of tasks to processing elements in a distributed system such that the total execution time is minimized. One approach for solving the scheduling problem is task clustering. This involves assigning tasks to clusters where each cluster is run on a single processor. This paper aims to show the feasibility of using Genetic Algorithms for task clustering to solve the scheduling problem. Genetic Algorithms are robust optimization and search techniques that are used in this work to solve the task-clustering problem. The proposed approach shows great promise to solve the clustering problem for a wide range of clustering instances.

We consider an online model where an adversary constructs a set of $2^s$ instances $S$ instead of one single instance. The algorithm knows $S$ and the adversary will choose one instance from $S$ at random to present to the algorithm. We further focus on adversaries that construct sets of $k$-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in $s$ and matching upper and lower bound are given for a specific set of algorithms that we call “minimalistic online algorithms”.

The inertial driving behavior, although observed in real traffic, has not been deeply understood in most previous studies. In this paper we propose a cellular automata model of the traffic on a single lane highway which considers the drivers' inertial behavior under different driving circumstances. Simulation results show that our model can capture such important features of the traffic as jam formation, phase transition and metastable states. Some of other models, like the slow-to-start model, can be derived from our model.

The quality of randomization of Chinese randomized trials on herbal medicines for hepatitis B was assessed. Search strategy and inclusion criteria were based on the published protocol. One hundred and seventy-six randomized clinical trials (RCTs) involving 20,452 patients with chronic hepatitis B virus (HBV) infection were identified that tested Chinese medicinal herbs. They were published in 49 Chinese journals. Only 10% (18/176) of the studies reported the method by which they randomized patients. Only two reported allocation concealment and were considered as adequate. Twenty percent (30/150) of the studies were imbalanced at the 0.05 level of probability for the two treatments and 13.3% (20/150) imbalanced at the 0.01 level in the randomization. It is suggested that there may exist misunderstanding of the concept and the misuse of randomization based on the review.

This paper deals with randomization methods for valuing American options written on dividend-paying assets, which are based on the idea of treating the maturity date as a random variable. In the randomization method introduced by Carr in 1998, he used the Erlangian distributed random variable to develop a recursive algorithm starting from the so-called Canadian option with an exponentially distributed random maturity. The purposes of this paper are (i) to provide much simpler pricing formulas for the Canadian option; (ii) to interpret the Gaver–Stehfest method developed for inverting Laplace transforms as an alternative randomization method in the context of valuing American options; and (iii) to evaluate the performance of the Gaver–Stehfest method in details with theoretical and numerical views. Numerical experiments indicate that the Gaver–Stehfest method works well to generate accurate approximations for the early exercise boundary as well as the option value.

“Period three implications” are investigated for a large class of multivalued maps on the circle. The obtained Sharkovsky–Block–Siegberg type theorem is then applied to differential equations and inclusions for the coexistence of infinitely many derivo–periodic solutions with various periods, sometimes called subharmonic solutions of the second kind. These deterministic results are also randomized. Several illustrative examples are supplied.

A multivalued version of the well-known (Sharkovsky type) Block cycle coexistence theorem is, on the basis of our former results, completed and applied to differential equations and inclusions. The deterministic results are also randomized which allows us, besides other things, to eliminate some exceptional absent periodic dynamics. In this way, instead of at most two possible deterministic exceptional cases (w.r.t. the standard Block theorem), only one possible random exception can occur, provided the forcing period $n=2^m\cdot 3$, $m\in \mathbb{N}\cup \{0\}$. On the other hand, the application to random differential equations and inclusions is not so effective in general.

With increasing need for preserving confidential data while providing recommendations, privacy-preserving collaborative filtering has been receiving increasing attention. To make data owners feel more comfortable while providing predictions, various schemes have been proposed to estimate recommendations without deeply jeopardizing privacy. Such methods eliminate or reduce data owners' privacy, financial, and legal concerns by employing different privacy-preserving techniques. Although there are considerable numbers of studies focusing on privacy-preserving collaborative filtering schemes, there is no comprehensive survey investigating them with respect to different directions. In this survey, we mainly focus on studying various privacy-preserving recommendation methods according to the data partitioning cases and the utilized techniques for preserving confidentiality. We also review privacy in general and examine in collaborative filtering scenarios. We discuss the proposed schemes in terms of their limitations and practical implementation challenges. Moreover, we give an overview of evaluation of such schemes. We finally provide a comprehensive guideline for studying in this area and propose future research directions.

With the popularity of social networks, privacy issues with regard to publishing social network data have gained intensive focus from academia. We analyzed the current privacy-preserving techniques for publishing social network data and defined a privacy-preserving model with privacy guarantee $k$. With our definitions, the existing privacy-preserving methods, $k$-anonymity and randomization can be combined together to protect data privacy. We also considered the privacy threat with label information and modify the $k$-anonymity technique of tabular data to protect the published data from being attacked by the combination of two types of background knowledge, the structural and label knowledge. We devised a partial $k$-anonymity algorithm and implemented it in Python and open source packages. We compared the algorithm with related $k$-anonymity and random techniques on three real-world datasets. The experimental results show that the partial $k$-anonymity algorithm preserves more data utilities than the $k$-anonymity and randomization algorithms.

We present a robust implementation of the Beneath-Beyond algorithm for computing convex hulls in arbitrary dimension. Certain techniques used are of independent interest in the implementation of geometric algorithms. In particular, two important, and often complementary, issues are studied, namely exact arithmetic and degeneracy. We focus on integer arithmetic and propose a general and efficient method for its implementation based on modular arithmetic. We suggest that probabilistic modular arithmetic may be of wide interest, as it combines the advantages of modular arithmetic with the speed of randomization. The use of perturbations as a method to cope with input degeneracy is also illustrated. A computationally efficient scheme is implemented which, moreover, greatly simplifies the task of programming. We concentrate on postprocessing, often perceived as the Achilles' heel of perturbations. Experimental results illustrate the dependence of running time on the various input parameters and attempt a comparison with existing programs. Lastly, we discuss the visualization capabilities of our software and illustrate them for problems in computational algebraic geometry. All code is publicly available.

This paper presents an implementation for Delaunay triangulations of three-dimensional point sets. The code uses a variant of the randomized incremental flip algorithm and employs symbolic perturbation to achieve robustness. The algorithm's theoretical time complexity is quadratic in n, the number of input points, and this is optimal in the worst case. However, empirical running times are proportional to the number of triangles in the final triangulation, which is typically linear in n. Even though the symbolic perturbation scheme relies on exact arithmetic, the resulting code is efficient in practice. This is due to a careful implementation of the geometric primitives and the arithmetic module. The source code is available on the Internet.

Recently, there has been much interest in enhancing purely combinatorial formalisms with numerical information. For example, planning formalisms can be enriched by taking resource constraints and probabilistic information into account. The Mixed Integer Programming (MIP) paradigm from operations research provides a natural tool for solving optimization problems that combine such numeric and non-numeric information. The MIP approach relies heavily on linear program relaxations and branch-and-bound search. This is in contrast with depth-first or iterative deepening strategies generally used in artificial intelligence. We provide a detailed characterization of the structure of the underlying search spaces as explored by these search strategies. Our analysis shows that much can be gained by combining different search strategies for solving hard MIP problems, thereby leveraging each strategy's strength in terms of the combinatorial and numeric information.

Two deterministic Sharkovsky-type theorems on the circle due to L. Block [Proc. Amer. Math. Soc.82 (1981) 481–486] and X. Zhao [Fixed Point Theory Appl., Article ID 194875 (2008)] are randomized. The randomization of Block’s theorem brings an additional information about the forcing alternatives. Some further possibilities of the randomized Zhao’s theorem are discussed for multivalued maps.

The random Dirichlet type functions on the unit ball of Cⁿ are studied. Sufficient conditions of the multipliers of for 0 < μ ≤ 1, if n = 1 or 0 < μ < 2 if n > 1 are given. The smoothness of random Dirichlet type functions is discussed.

The notion of a randomization of a first-order structure was introduced by Keisler in the paper Randomizing a Model, Advances in Math. 1999. The idea was to form a new structure whose elements are random elements of the original first-order structure. In this paper we treat randomizations as continuous structures in the sense of Ben Yaacov and Usvyatsov. In this setting, the earlier results show that the randomization of a complete first-order theory is a complete theory in continuous logic that admits elimination of quantifiers and has a natural set of axioms. We show that the randomization operation preserves the properties of being omega-categorical, omega-stable, and stable.

Suppose that we are given a set of n elements d of which have a property called defective. A group test can check for any subset, called a pool, whether it contains a defective. It is known that a nearly optimal number of O(d log (n/d)) pools in two stages (where tests within a stage are done in parallel) are sufficient, but then the searcher must know d in advance. Here we explore group testing strategies that use a nearly optimal number of pools and a few stages although d is not known beforehand. We prove a lower bound of Ω(log d/log log d) stages and more general pools versus stages tradeoff. This is almost tight, since O(log d) stages are sufficient for a strategy with O(d log n) pools. As opposed to this negative result, we devise a randomized strategy using O(d log (n/d)) pools in three stages, with any desired success probability 1-ϵ. With some additional measures even two stages are enough. Open questions concern the optimal constant factors and practical implications. A related problem motivated by biological network analysis is to learn hidden vertex covers of a small size k in unknown graphs by edge group tests. (Does a given subset of vertices contain an edge?) We give a one-stage strategy using O(k³log n) pools, with any parameterized algorithm for vertex cover enumeration as a decoder. During the course of this work we also provide a classification of types of randomized search strategies in general.

Group testing is the problem of finding d defectives in a set of n elements, by asking carefully chosen subsets (pools) whether they contain defectives. Strategies are preferred that use both a small number of tests close to the information-theoretic lower bound d log₂ n, and a small constant number of stages, where tests in every stage are done in parallel, in order to save time. They should even work if d is not known in advance. In fact, one can succeed with O(d log n) queries in two stages, if certain tests are randomized and a constant failure probability is allowed. An essential ingredient of such strategies is to get an estimate of d within a constant factor. This problem is also interesting in its own right. It can be solved with O(log n) randomized group tests of a certain type. We prove that Ω(log n) tests are also necessary, if elements for the pools are chosen independently. The proof builds upon an analysis of the influence of tests on the searcher's ability to distinguish between any two candidate numbers with a constant ratio. The next challenge is to get optimal constant factors in the O(log n) test number, depending on the prescribed error probability and the accuracy of d. We give practical methods to derive upper bound tradeoffs and conjecture that they are already close to optimal. One of them uses a linear programming formulation.

For adaptive clinical trials using a generalized Friedman's urn design, we derive the limiting distribution of the urn composition under staggered entry and delayed response. The stochastic delay mechanism is assumed to depend on both the treatment assigned and the patient's response. A very general setup is employed with K treatments and L responses. When L = K = 2, one example of a generalized Friedman's urn design is the randomized play-the-winner rule. An application of this rule occurred in a clinical trial of depression, which had staggered entry and delayed response. We show that maximum likelihood estimators from such a trial have the usual asymptotic properties.

Adaptive randomization is used to support the statistical methodology of a clinical trial by maintaining balance among treatments for the analysis population and subgroups (or strata). With this technology individual subject response information is maximized, especially important for studies involving rare conditions, terminally ill patients, and for studies terminated early.

In determining the random adaptive algorithm the clinical trial statistician considers the statistical methodology, or model statement, to be used for the primary efficacy variable. Prognostic factors are incorporated into the random adaptive algorithm in a parallel design to best support the planned statistical analyses. Theoretical frameworks are either frequentist or Bayesian.

The process of developing the random adaptive module of the automated randomization system is delineated including re-sequencing, re-randomization and reporting of randomization transactions. Implementation of an adaptive randomization is relatively easy so that efficiencies of design to achieve balances which support the statistical analysis and reporting accountability are well worth the implementation effort.

Interactive Clinical Technologies Incorporated (ICTI) has been implementing adaptive randomization designs in clinical trials since 1999 and has participated in over 75 adaptive randomization studies of varying complexity.