Closing ranks in rigid multi‐agent formations using edge contraction

This paper proposes a systematic approach to solve the closing rank problem for a rigid multi‐agent formation, viz. restoring rigidity after loss of an agent. The approach is based on a particular graph operation, the edge contraction operation. It is proven that when an agent is lost in an arbitrary two‐dimensional rigid formation, rigidity can always be restored by transferring all links to which this agent was incident on to one of its neighbors, though not in general any arbitrary one of them. From a graph theoretical point of view, this corresponds to contraction of a certain edge incident to the vertex representing the agent being lost. It is established, for any two‐dimensional rigid formation (graph), that there exists at least two such edges that can be contracted to solve the closing ranks problem. Later, it is demonstrated that any potential decentralized algorithm to check if an arbitrary edge is contractible would need to use information on vertices and edges that can be at arbitrarily large distance from the edge considered; and a set of rigid graph theoretical results are established for several general settings, which can be used in selection of the edge to contract in these settings in order to solve the corresponding closing ranks problems. Partial results are also obtained for three‐dimensional formations, and it is shown that the two‐dimensional results do not generalize as such to higher dimension. Copyright © 2010 John Wiley & Sons, Ltd.     

Philosophy of the M<Emphasis Type="SmallCaps">ini</Emphasis>Z<Emphasis Type="SmallCaps">inc</Emphasis> challenge

MiniZinc arose as a response to the extended discussion at CP2006 of the need for a standard modelling language for CP. This is a challenging problem, and we believe MiniZinc makes a good attempt to handle the most obvious obstacle: there are hundreds of potential global constraints, most handled by few or no systems. A standard input language for solvers gives us the capability to compare different solvers. Hence, every year since 2008 we have run the MiniZinc Challenge comparing different solvers that support MiniZinc. In this report we discuss the philosophy behind the challenge, why we do it, how we do it, and why we do it that way.     

Organization of digital resources as an original facet for exploring the quiescent information capital of a community

Knowledge workers organize the documents they need for daily task achievement in their personal information spaces (PISs). For a community, people’s PISs constitute in-house value-added resources. Paradoxically, this information source is poorly exploited, as people tend to use external sources (e.g., the Web), although this is probably poorly appropriate in corporate context. This article tackles such information access issues in the common context. Our contribution consists in a faceted visual interface to explore various facets (points of view) of the information of a community, which remains quiescent otherwise. Besides common facets only based on information contents, we propose a new facet relying on the way users in a community manage and organize information. As a result, our approach exploits knowledge workers’ efforts devoted to PIS management, turning them to profit for all, by fostering mutual benefit between stakeholders. The proposed facet relies on an original organization-based similarity measure that we define and experiment.     

Information theoretic combination of pattern classifiers

Combining several classifiers has proved to be an effective machine learning technique. Two concepts clearly influence the performances of an ensemble of classifiers: the diversity between classifiers and the individual accuracies of the classifiers. In this paper we propose an information theoretic framework to establish a link between these quantities. As they appear to be contradictory, we propose an information theoretic score (ITS) that expresses a trade-off between individual accuracy and diversity. This technique can be directly used, for example, for selecting an optimal ensemble in a pool of classifiers. We perform experiments in the context of overproduction and selection of classifiers, showing that the selection based on the ITS outperforms state-of-the-art diversity-based selection techniques.     

Global land surface phenology trends from GIMMS database

A double logistic function has been used to describe global inventory mapping and monitoring studies (GIMMS) normalized difference vegetation index (NDVI) yearly evolution for the 1981 to 2003 period, in order to estimate land surface phenology parameter. A principal component analysis on the resulting time series indicates that the first components explain 36, 53 and 37% of the variance for the start, end and length of growing season, respectively, and shows generally good spatial homogeneity. Mann–Kendall trend tests have been carried out, and trends were estimated by linear regression. Maps of these trends show a global advance in spring dates of 0.38 days per year, a global delay in autumn dates of 0.45 days per year and a global increase of 0.8 days per year in the growing seasons validated by comparison with previous works. Correlations between retrieved phenological parameters and climate indices generally showed a good spatial coherence.     

Surface deformation models for nonrigid 3D shape recovery

Three-dimensional detection and shape recovery of a nonrigid surface from video sequences require deformation models to effectively take advantage of potentially noisy image data. Here, we introduce an approach to creating such models for deformable 3D surfaces. We exploit the fact that the shape of an inextensible triangulated mesh can be parameterized in terms of a small subset of the angles between its facets. We use this set of angles to create a representative set of potential shapes, which we feed to a simple dimensionality reduction technique to produce low-dimensional 3D deformation models. We show that these models can be used to accurately model a wide range of deforming 3D surfaces from video sequences acquired under realistic conditions.     

Integrating digital topology in image-processing libraries

This paper describes a method to integrate digital topology informations in image-processing libraries. This additional information allows a library user to write algorithms respecting topological constraints, for example, a seed fill or a skeletonization algorithm. As digital topology is absent from most image-processing libraries, such constraints cannot be fulfilled. We describe and give code samples for all the structures necessary for this integration, and show a use case in the form of a homotopic thinning filter inside ITK. The obtained filter can be up to a hundred times as fast as ITK's thinning filter and works for any image dimension. This paper mainly deals of integration within ITK, but can be adapted with only minor modifications to other image-processing libraries.     

Permutation flowshop scheduling problems with maximal and minimal time lags

In this paper, we study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m$m$-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.     

On the efficiency of several VM provisioning strategies for workflows with multi-threaded tasks on clouds

Cloud computing promises the delivery of on-demand pay-per-use access to unlimited resources. Using these resources requires more than a simple access to them as most clients have certain constraints in terms of cost and time that need to be fulfilled. Therefore certain scheduling heuristics have been devised to optimize the placement of client tasks on allocated virtual machines. The applications can be roughly divided in two categories: independent bag-of-tasks and workflows. In this paper we focus on the latter and investigate a less studied problem, i.e., the effect the virtual machine allocation policy has on the scheduling outcome. For this we look at how workflow structure, execution time, virtual machine instance type affect the efficiency of the provisioning method when cost and makespan are considered. To aid our study we devised a mathematical model for cost and makespan in case single or multiple instance types are used. While the model allows us to determine the boundaries for two of our extreme methods, the complexity of workflow applications calls for a more experimental approach to determine the general relation. For this purpose we considered synthetically generated workflows that cover a wide range of possible cases. Results have shown the need for probabilistic selection methods in case small and heterogeneous execution times are used, while for large homogeneous ones the best algorithm is clearly noticed. Several other conclusions regarding the efficiency of powerful instance types as compared to weaker ones, and of dynamic methods against static ones are also made.