Static worksharing strategies for heterogeneous computers with unrecoverable interruptions

One has a large computational workload that is “divisible” (its constituent tasks’ granularity can be adjusted arbitrarily) and one has access to p remote computers that can assist in computing the workload. How can one best utilize the computers? Two features complicate this question. First, the remote computers may differ from one another in speed. Second, each remote computer is subject to interruptions of known likelihood that kill all work in progress on it. One wishes to orchestrate sharing the workload with the remote computers in a way that maximizes the expected amount of work completed. We deal with three versions of this problem. The simplest version ignores communication costs but allows computers to differ in speed (a heterogeneous set of computers). The other two versions account for communication costs, first with identical remote computers (a homogeneous set of computers), and then with computers that may differ in speed. We provide exact expressions for the optimal work expectation for all three versions of the problem - via explicit closed-form expressions for the first two versions, and via a recurrence that computes this optimal value for the last, most general version.     

Preparation et caracterisation des ferrites de calcium CaFe2+nO4+n a valeurs fractionnaires de n (32, 52) et leur incidence sur le diagramme Fe-Ca-O A 1120°C

The synthesis of two new calcium ferrites belonging to the CaFe_2+nO_4+n family, with the fractional values $\text{n =}\text{3}\text{2}$ and $\text{5}\text{2}$, has been done.Their crystalline structures have been determined. A stacking process of blocks with the CaFe₂O₄ composition and blocks with the FeO composition, like for the other terms of the series with n integer (1, 2, 3) allows to describe them.The schematic representation of this new example of intergrowth has been carried out according to A.F. Wells' method.The existence of these ferrites has lead us to specify the Fe-Ca-O diagram at 1120°C in the FeO-Ca₂Fe₂O₅-CaFe₂O₄ - Fe₃O₄ region.     

A dynamics formulation of general constrained robots

The complexity of a standard compact-in-form Lagrangian dynamical expression is proportional to the fourth power of the number of degrees of freedom (DOF) of a robotic system. This fact challenges both simulation and control of robots with hyper degrees of freedom. In this paper, a systematic approach for deriving the dynamical expression of so-called general constrained robots is proposed. This proposed approach has two main features. First, it uses the subsystem dynamics such as the dynamics of joints and rigid links to construct the dynamical expression of the entire robotic system in a closed form. The complexity of the resulted dynamic expression is linearly proportional to the number of DOF of a robotic system. Second, it extends the standard dynamical form and properties of the conventional single-arm constrained robots to a class of more general robotic systems including the coordinated multiple-arm robotic systems. Three spaces, namely the general joint space, the general task space, and the extended subsystems space, are connected through corresponding velocity/force mapping matrices.An erratum to this article can be found at     

Hedging Point for Non-Markovian Piecewise Deterministic Production Processes

We consider a single non-markovian failure prone machine which delivers a single product. The operating policy of the machine is chosen to be of the hedging point type. In the infinite horizon limit, we calculate the position of the hedging point that minimizes a convex cost function.     

Solving subgraph isomorphism problems with constraint programming

The subgraph isomorphism problem consists in deciding if there exists a copy of a pattern graph in a target graph. We introduce in this paper a global constraint and an associated filtering algorithm to solve this problem within the context of constraint programming. The main idea of the filtering algorithm is to label every node with respect to its relationships with other nodes of the graph, and to define a partial order on these labels in order to express compatibility of labels for subgraph isomorphism. This partial order over labels is used to filter domains. Labelings can also be strengthened by adding information from the labels of neighbors. Such a strengthening can be applied iteratively until a fixpoint is reached. Practical experiments illustrate that our new filtering approach is more effective on difficult instances of scale free graphs than state-of-the-art algorithms and other constraint programming approaches.     

A URI-based approach for addressing fragments of media resources on the Web

To make media resources a prime citizen on the Web, we have to go beyond simply replicating digital media files. The Web is based on hyperlinks between Web resources, and that includes hyperlinking out of resources (e.g., from a word or an image within a Web page) as well as hyperlinking into resources (e.g., fragment URIs into Web pages). To turn video and audio into hypervideo and hyperaudio, we need to enable hyperlinking into and out of them. The W3C Media Fragments Working Group is taking on the challenge to further embrace W3C??s mission to lead the World Wide Web to its full potential by developing a Media Fragment protocol and guidelines that ensure the long-term growth of the Web. The major contribution of this paper is the introduction of Media Fragments as a media-format independent, standard means of addressing media resources using URIs. Moreover, we explain how the HTTP protocol can be used and extended to serve Media Fragments and what the impact is for current Web-enabled media formats.     

Changes in land surface temperatures and NDVI values over Europe between 1982 and 1999

We used land surface temperature (LST) algorithms and NDVI values to estimate changes in vegetation in the European continent between 1982 and 1999 from the Pathfinder AVHRR Land (PAL) dataset. These two parameters are monitored through HANTS (Harmonic ANalysis of Time Series) software, which allows the simultaneous observation of mean value, first harmonic amplitude and phase behaviors in the same image. These results for each complete year of data show the effect of volcanic aerosols and orbital drift on PAL data. Comparison of time series of HANTS cloud-free time series with the original time series for various land cover proves that this software is useful for LST analysis, although primarily designed for NDVI applications. Comparison of yearly averages of HANTS LST over the whole Europe with air temperature confirms the validity of the results. Maps of the evolution for both parameters between periods 1982/1986 and 1995/1999 have been elaborated: NDVI data show the well confirmed trend of increase over Europe (up to 0.1 in NDVI), Southern Europe seeing a decrease in NDVI (− 0.02). LST averages stay stable or slightly decrease (up to − 1.5 K) over the whole continent, except for southern areas for which the increase is up to 2.5 K. These results evidence that arid and semi-arid areas of Southern Europe have become more arid, the rest of Europe seeing an increase in its wood land proportion, while seasonal amplitude in Northern Europe has decreased.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

Throughput optimization in two-machine flowshops with flexible operations

In this study, a two-machine flowshop producing identical parts is considered. Each of the identical parts is assumed to require a number of manufacturing operations, and the machines are assumed to be flexible enough to perform different operations. Due to economical or technological constraints, some specific operations are preassigned to one of the machines. The remaining operations, called flexible operations, can be performed on either one of the machines, so that the same flexible operation can be performed on different machines for different parts. The problem is to determine the assignment of the flexible operations to the machines for each part, with the objective of maximizing the throughput rate. We consider various cases regarding the number of parts to be produced and the capacity of the buffer between the machines. We present solution methods for each variant of the problem.