Software-based study of a non-sorting method for median calculation on a set of integer numbers

This paper presents a software-based study of a hardware-based non-sorting median calculation method on a set of integer numbers. The method divides the binary representation of each integer element in the set into bit slices in order to find the element located in the middle position. The method exhibits a linear complexity order and our analysis shows that the best performance in execution time is obtained when slices of 4-bit in size are used for 8-bit and 16-bit integers, in mostly any data set size. Results suggest that software implementation of bit slice method for median calculation outperforms sorting-based methods with increasing improvement for larger data set size. For data set sizes of N > 5, our simulations show an improvement of at least 40%.

Bit-index sort: a fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred as Bit-index sort, which is a non-comparison sorting algorithm for partial per-mutations, with linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers supported by machine hardware to retrieve the ordered output sequence. Results show that Bit-index sort outperforms in execution time to quicksort and counting sort algorithms. A parallel approach for Bit-index sort using two simultaneous threads is included, which obtains speedups up to 1.6.

Generalised golden ratios over integer alphabets

It is a well known result that for β ∈ (1,1+√52) and x ∈ (0,1β−1) there exists uncountably many (ǫi)∞i=1 ∈ {0,1}N such that x = P∞i=1ǫiβ−i. When β ∈ (1+√52,2] there exists x ∈ (0,1β−1) for which there exists a unique (ǫi)∞i=1 ∈ {0,1}N such that x=P∞i=1ǫiβ−i. In this paper we consider the more general case when our sequences are elements of {0, . . . , m}N. We show that an analogue of the golden ratio exists and give an explicit formula for it.

Preconditioning 2D integer data for fast convex hull computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

Integer and fractional microwave induced resistance oscillations in a 2D system with moderate mobility

We report on integer and fractional microwave-induced resistance oscillations in a 2D electron system with high density and moderate mobility, and present results of measurements at high microwave intensity and temperature. Fractional microwave-induced resistance oscillations occur up to fractional denominator 8 and are quenched independently of their fractional order. We discuss our results and compare them with existing theoretical models. (C) 2009 Elsevier B.V. All rights reserved.

Combining extension matrix and integer programming for optimal concept learning

This paper proposes two integer programming models and their GA-based solutions for optimal concept learning. The models are built to obtain the optimal concept description in the form of propositional logic formulas from examples based on completeness, consistency and simplicity. The simplicity of the propositional rules is selected as the objective function of the integer programming models, and the completeness and consistency of the concept are used as the constraints. Considering the real-world problems that certain level of noise is contained in data set, the constraints in model 11 are slacked by adding slack-variables. To solve the integer programming models, genetic algorithm is employed to search the global solution space. We call our approach IP-AE. Its effectiveness is verified by comparing the experimental results with other well- known concept learning algorithms: AQ15 and C4.5.

Granularity and disaggregation in compositional modelling with applications to ecological systems

In the past decade, compositional modelling (CM) has established itself as the predominant knowledge-based approach to construct mathematical (simulation) models automatically. Although it is mainly applied to physical systems, there is a growing interest in applying CM to other domains, such as ecological and socio-economic systems. Inspired by this observation, this paper presents a method for extending the conventional CM techniques to suit systems that are fundamentally presented by interacting populations of individuals instead of physical components or processes. The work supports building model repositories for such systems, especially in addressing the most critical outstanding issues of granularity and disaggregation in ecological systems modelling.

α2β1 integrin affects metastatic potential of ovarian carcinoma spheroids by supporting disaggregation and proteolysis

Background: Ovarian cancer is characterized by a wide-spread intra-abdominal metastases which represents a major clinical hurdle in the prognosis and management of the disease. A significant proportion of ovarian cancer cells in peritoneal ascites exist as multicellular aggregates or spheroids. We hypothesize that these cellular aggregates or spheroids are invasive with the capacity to survive and implant on the peritoneal surface. This study was designed to elucidate early inherent mechanism(s) of spheroid survival, growth and disaggregation required for peritoneal metastases.

Methods: In this study, we determined the growth pattern and adhesive capacity of ovarian cancer cell lines (HEY and OVHS1) grown as spheroids, using the well established liquid overlay technique, and compared them to a normal ovarian cell line (IOSE29) and cancer cells grown as a monolayer. The proteolytic capacity of these spheroids was compared with cells grown as a monolayer using a gelatin zymography assay to analyze secreted MMP-2/9 in conditioned serum-free medium. The disaggregation of cancer cell line spheroids was determined on extracellular matrices (ECM) such as laminin (LM), fibronectin (FN) and collagen (CI) and the expression of α2, α3, αv, α6 and β1 interin was determined by flow cytometric analysis. Neutralizing antibodies against α2, β1 subunits and α2β1 integrin was used to inhibit disaggregation as well as activation of MMPs in spheroids.

Results: We demonstrate that ovarian cancer cell lines grown as spheroids can sustain growth for 10 days while the normal ovarian cell line failed to grow beyond 2 days. Compared to cells grown as a monolayer, cancer cells grown as spheroids demonstrated no change in adhesion for up to 4 days, while IOSE29 cells had a 2–4-fold loss of adhesion within 2 days. Cancer cell spheroids disaggregated on extracellular matrices (ECM) and demonstrated enhanced expression of secreted pro-MMP2 as well as activated MMP2/MMP9 with no such activation of MMP's observed in monolayer cells. Flow cytometric analysis demonstrated enhanced expression of α2 and diminution of α6 integrin subunits in spheroids
versus monolayer cells. No change in the expression of α3, αv and β1 subunits was evident. Conversely, except for αv integrin, a 1.5–7.5-fold decrease in α2, α3, α6 and β1 integrin subunit expression was observed in IOSE29 cells within 2 days. Neutralizing antibodies against α2, β1 subunits and α2β1 integrin inhibited disaggregation as well as activation of
MMPs in spheroids.

Conclusion: Our results suggest that enhanced expression of α2β1 integrin may influence spheroid disaggregation and
proteolysis responsible for the peritoneal dissemination of ovarian carcinoma. This may indicate a new therapeutic target
for the suppression of the peritoneal metastasis associated with advanced ovarian carcinomas.

Polyhedral studies for minimum-span graph labelling with integer distance constraints

This paper studies the polytope of the minimum-span graph labelling problems with integer distance constraints (DC-MSGL). We first introduce a few classes of new valid inequalities for the DC-MSGL defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch-and-cut algorithm for solving the DC-MSGL. Following that, we present our polyhedral results on the dimension of the DC-MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC-MSGL on triangular graphs.

Disaggregation of household energy consumption patterns in Australian

Improving energy efficiency is an important target to be achieved in residential building development and household behaviour. The aim of this research is to help building professionals and policy makers understand the current housing situations and householders’ behaviour regarding energy consumption. The results of a survey of energy consumption, including house situations and householder behaviour, of 504 households in New South Wales Australia are reported. Twelve features affecting household energy consumption are investigated. These features included cooking appliances, refrigerators, laundry appliances, televisions, computers, gaming consoles, hot water systems, space cooling and heating systems, glazing, insulation, lighting, and other major energy consumption facilities. The differences of these features across different households with different physical characteristics, social-demographic features and geographical areas are analyzed. Based on the disaggregate study, it is found that mandatory policy, geographical and socio-economic factors can significantly affect the selection of fixtures and appliances in the households. It is also found that the positive effect of the government’s mandatory policy implementation on household energy consumption behaviour is evidenced. The findings will be of use in sustainable residential building development policy-making, and tailoring the regulations and standards with consideration of the various geographical and socio-economic factors.