Correctness proof of an in-place permutation

The correctness of an in-place permutation algorithm is proved. The algorithm exchanges elements belonging to a permutation cycle. A suitable assertion is constructed from which the correctness can be deduced after completion of the algorithm.An in-place rectangular matrix transposition algorithm is given as an example.     

Extended connectivity in chemical graphs

The true nature of the extended connectivity, used in Morgan algorithm for the canonical numerotation of points in chemical graphs, is discussed. An alternative method for its calculation based on the number of walks is described and shown to yield results identical to Morgan's method.     

Proper Framework for the Application of Power Management Algorithms

A power aware system can reduce its energy dissipation by dynamically powering off during idle periods and powering on again upon a new service request arrival. We minimize the dissipated energy, by selecting the optimal waiting interval before powering off, under consideration of the expected time of the next arrival. This approach has been already proposed in the past, using the idle times distribution, rather than the interarrival periods captured at the moment of service completion. Algorithms proposed in the literature utilize the history of idle periods or assume a vanishing service time. There has been no clear proposition on how service time affects the time instance of our power off decision; rather, whenever service time has been significant, a “blurred” image of the system’s characteristic and a corresponding approximated optimal policy occurred. We clearly show analytically and experimentally that the idle times distribution should not be used as a primary design input, since it is the product of two separate inputs; the interarrival times and the service times. We give insight to our problem, using a mechanical equivalent established at the moment of service completion of all pending requests and show through analytical examples how service time affects our power-off decision. We explain the paradox of being advantageous to wait for intervals more than the shutdown threshold (which is a system characteristic) and show how the introduction of idle period lengths instead of interarrival periods “blurs” the input distribution, leading to non-optimal decisions. Our contribution is to define and solve the proper problem, solely relying on the interarrival distribution. Further, we examine the problem under the framework of competitive analysis. We show how the interarrival distribution that maximizes the competitive ratio, being an exponential distribution, intervenes with power management; it renders the optimization procedure worthless through its “memoryless property”. Exponential interarrivals, irrespective of the service time pattern, are the marginal case where we cannot obtain energy gains. In all other cases the framework we promote ensures considerable advantages compared to other approaches in the literature. Moreover, it leads to a self contained module, implementable in software or hardware, which is based on an iterative formula and thus reduces power management calculations significantly. Here we exploit all operational features of the problem in proposing an implementation which spreads computations over the whole of the waiting period. We extensively compare our results numerically both against claimed expectations and against previous proposals. The outcome fully supports our framework as the one most appropriate for the application of power management.Part of this work has been supported by the EU IST-2001-34157 project PACKWOMAN (Power Aware Communication for Wireless Optimised Personal Area Networks).     

Design and Analysis of an Efficient Communication Strategy for Hierarchical and Highly Changing Ad-hoc Mobile Networks

In this work we introduce two practical and interesting models of ad-hoc mobile networks: (a) hierarchical ad-hoc networks, comprised of dense subnetworks of mobile users interconnected by a very fast yet limited backbone infrastructure, (b) highly changing ad-hoc networks, where the deployment area changes in a highly dynamic way and is unknown to the protocol. In such networks, we study the problem of basic communication, i.e., sending messages from a sender node to a receiver node. For highly changing networks, we investigate an efficient communication protocol exploiting the coordinated motion of a small part of an ad-hoc mobile network (the runners support) to achieve fast communication. This protocol instead of using a fixed sized support for the whole duration of the protocol, employs a support of some initial (small) size which adapts (given some time which can be made fast enough) to the actual levels of traffic and the (unknown and possibly rapidly changing) network area, by changing its size in order to converge to an optimal size, thus satisfying certain Quality of Service criteria. Using random walks theory, we show that such an adaptive approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple non-adaptive implementation of the basic runners support idea, introduced in [9,10]. For hierarchical ad-hoc networks, we establish communication by using a runners support in each lower level of the hierarchy (i.e., in each dense subnetwork), while the fast backbone provides interconnections at the upper level (i.e., between the various subnetworks). We analyze the time efficiency of this hierarchical approach. This analysis indicates that the hierarchical implementation of the support approach significantly outperforms a simple implementation of it in hierarchical ad-hoc networks. Finally, we discuss a possible combination of the two approaches above (the hierarchical and the adaptive ones) that can be useful in ad-hoc networks that are both hierarchical and highly changing. Indeed, in such cases the hierarchical nature of these networks further supports the possibility of adaptation.     

Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

A time-decomposition algorithm for a stiff linear two-point boundary-value problem and its application to a nonlinear optimal control problem

An algorithm is proposed to solve a stiff linear two-point boundary-value problem (TPBVP). In a stiff problem, since some particular solutions of the system equation increase and others decrease rapidly as the independent variable changes, the integration of the system equation suffers from numerical errors. In the proposed algorithm, first, the overall interval of integration is divided into several subintervals; then, in each subinterval a sub-TPBVP with arbitrarily chosen boundary values is solved. Second, the exact boundary values which guarantee the continuity of the solution are determined algebraically. Owing to the division of the integration interval, the numerical error is effectively reduced in spite of the stiffness of the system equation. It is also shown that the algorithm is successfully imbedded into an interaction-coordination algorithm for solving a nonlinear optimal control problem.The authors would like to thank Mr. T. Sera and Mr. H. Miyake for their help with the calculations.     

Optimal control of coupled spin dynamics: design of NMR pulse sequences by gradient ascent algorithms

In this paper, we introduce optimal control algorithm for the design of pulse sequences in NMR spectroscopy. This methodology is used for designing pulse sequences that maximize the coherence transfer between coupled spins in a given specified time, minimize the relaxation effects in a given coherence transfer step or minimize the time required to produce a given unitary propagator, as desired. The application of these pulse engineering methods to design pulse sequences that are robust to experimentally important parameter variations, such as chemical shift dispersion or radiofrequency (rf) variations due to imperfections such as rf inhomogeneity is also explained.     

Partially dynamic maintenance of minimum weight hyperpaths

We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such a problem, we provide a new efficient algorithm that works for a wide class of hyperpath weight measures. This algorithm explicitly updates minimum weight hyperpaths in

Full-size image

worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in and is the size of the representation of the hypergraph. Hyperpath weight measures are only required to belong to the class of strict weakly superior functions.     

Solving problems of discrete tomography

This is a summary of the most important results presented in the author's PhD thesis. This thesis, written in French, was defended on 24 November 2004 and supervised by Marie-Christine Costa and Christophe Picouleau. This thesis consists in developing the study of discrete tomography problems. It aims at reconstructing discrete objects (matrices, images, discrete sets, etc) that are accessible only through few projections. A copy of the thesis is available on "http: //cedric.cnam.fr/AfficheArticle.php?id = 698". Received: April 2005 AMS classification: 90B70, 68Q17, 52C15, 05B50     

A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with -iteration complexity

An interior point method for monotone linear complementarity problems acting in a wide neighborhood of the central path is presented. The method has -iteration complexity and is superlinearly convergent even when the problem does not possess a strictly complementary solution. Mathematics Subject Classification (2000): 49M15, 65K05, 90C33 Work supported by the National Science Foundation under Grant No. 0139701. An erratum to this article is available at.