New insights on integer-programming models for the kidney exchange problem

In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. The underlying optimization problems can be formulated as integer programming models. Previously proposed models for kidney exchange programs have exponential numbers of constraints or variables, which makes them fairly difficult to solve when the problem size is large. In this work we propose two compact formulations for the problem, explain how these formulations can be adapted to address some problem variants, and provide results on the dominance of some models over others. Finally we present a systematic comparison between our models and two previously proposed ones via thorough computational analysis. Results show that compact formulations have advantages over non-compact ones when the problem size is large.

Replica management in real-time Ada 95 applications

In this paper, we present some of the fault tolerance management mechanisms being implemented in the Multi-μ architecture, namely its support for replica non-determinism. In this architecture, fault tolerance is achieved by node active replication, with software based replica management and fault tolerance transparent algorithms. A software layer implemented between the application and the real-time kernel, the Fault Tolerance Manager (FTManager), is the responsible for the transparent incorporation of the fault tolerance mechanisms The active replication model can be implemented either imposing replica determinism or keeping replica consistency at critical points, by means of interactive agreement mechanisms. One of the Multi-μ architecture goals is to identify such critical points, relieving the underlying system from performing the interactive agreement in every Ada dispatching point.

Cantor exchange systems and renormalization

We prove a one-to-one correspondence between (i) C1+ conjugacy classes of C1+H Cantor exchange systems that are C1+H fixed points of renormalization and (ii) C1+ conjugacy classes of C1+H diffeomorphisms f with a codimension 1 hyperbolic attractor Lambda that admit an invariant measure absolutely continuous with respect to the Hausdorff measure on Lambda. However, we prove that there is no C1+alpha Cantor exchange system, with bounded geometry, that is a C1+alpha fixed point of renormalization with regularity alpha greater than the Hausdorff dimension of its invariant Cantor set.

Arc exchange systems and renormalization

We exhibit the construction of stable arc exchange systems from the stable laminations of hyperbolic diffeomorphisms. We prove a one-to-one correspondence between (i) Lipshitz conjugacy classes of C(1+H) stable arc exchange systems that are C(1+H) fixed points of renormalization and (ii) Lipshitz conjugacy classes of C(1+H) diffeomorphisms f with hyperbolic basic sets Lambda that admit an invariant measure absolutely continuous with respect to the Hausdorff measure on Lambda. Let HD(s)(Lambda) and HD(u)(Lambda) be, respectively, the Hausdorff dimension of the stable and unstable leaves intersected with the hyperbolic basic set L. If HD(u)(Lambda) = 1, then the Lipschitz conjugacy is, in fact, a C(1+H) conjugacy in (i) and (ii). We prove that if the stable arc exchange system is a C(1+HDs+alpha) fixed point of renormalization with bounded geometry, then the stable arc exchange system is smooth conjugate to an affine stable arc exchange system.