On the Kidney Exchange Problem and Online Minimum Energy Scheduling
Creators: Herrera Humphries, Tulia
Publisher: name: Columbia University
Year: 2014
Subjects: Operations research

description: The allocation and management of scarce resources are of central importance in the design
      of policies to improve social well-being. This dissertation consists of three essays; the first
      two deals with the problem of allocating kidneys and the third one on power management
      in computing devices.
      Kidney exchange programs are an attractive alternative for patients who need a kidney
      transplant and who have a willing, but medically incompatible, donor. A registry that keeps
      track of such patient-donor pairs can nd matches through exchanges amongst such pairs.
      This results in a quicker transplant for the patients involved, and equally importantly, keeps
      such patients from the long wait list of patients without an intended donor. As of March
      2014, there were at least 99,000 candidates waiting for a kidney transplant in the U.S.
      However, in 2013 only 16,893 transplants were conducted. This imbalance between supply
      and demand among other factors, has driven the development of multiple kidney exchange
      programs in the U.S. and the subsequent development of matching mechanisms to run the
      programs.
      In the first essay we consider a matching problem arising in kidney exchanges between
      hospitals. Focusing on the case of two hospitals, we construct a strategy-proof matching
      mechanism that is guaranteed to return a matching that is at least 3/4 the size of a maximum cardinality
      matching. It is known that no better performance is possible if one focuses on
      mechanisms that return a maximal matching, and so our mechanism is best possible within
      this natural class of mechanisms. For path-cycle graphs we construct a mechanism that
      returns a matching that is at least 4/5 the size of max-cardinality matching. This mechanism
      does not necessarily return a maximal matching. Finally, we construct a mechanism that is
      universally truthful on path-cycle graphs and whose performance is within 2/3 of optimal.
      Again, it is known that no better ratio is possible.
      In most of the existing literature, mechanisms are typically evaluated by their overall
      performance on a large exchange pool, based on which conclusions and recommendations
      are drawn. In our second essay, we consider a dynamic framework to evaluate extensively
      used kidney exchange mechanisms. We conduct a simulation-based study of a dynamically
      evolving exchange pool during 9 years. Our results suggest that some of the features that
      are critical in a mechanism in the static setting have only a minor impact in its longrun
      performance when viewed in the dynamic setting. More importantly, features that
      are generally underestimated in the static setting turn to be relevant when we look at
      dynamically evolving exchange pool. For example, the pairs' arrival rates. In particular we
      provide insights into the eect on the waiting times and the probability to receive an oer
      of controllable features such as the frequency at which matching are run, the structures
      through which pairs could be matched (cycles or chains) as well as inherent features such
      as the pairs ABO-PRA characteristics, the availability of altruistic donors, and wether or
      not compatible pairs join the exchange etc. We evaluate the odds to receive an oer and
      the expected time to receive an oer for each ABO-PRA type of pairs in the model.
      Power management in computing devices aims to minimize energy consumption to perform
      tasks, meanwhile keeping acceptable performance levels. A widely used power management
      strategy for devices, is to transit the devices and/or components to lower power
      consumption states during inactivity periods. Transitions between power states consume
      energy, thus, depending on such costs, it may be advantageous to stay in high power state
      during some inactivity periods. In our third essay we consider the problem of minimizing
      the total energy consumed by a 2-power state device, to process jobs that are sent over time
      by a constrained adversary. Jobs can be preempted, but deadlines need to be met. In this
      problem, an algorithm must decide when to schedule the jobs, as well as a sequence of power
      states, and the discrete time thresholds at which these states will be reached. We provide
      an online algorithm to minimize the energy consumption when the cost of a transition to
      the low power state is small enough. In this case, the problem of minimizing the energy
      consumption is equivalent to minimizing the total number of inactivity periods. We also
      provide an algorithm to minimize the energy consumption when it may be advantageous
      to stay in high power state during some inactivity periods. In both cases we provide upper
      bounds on the competitive ratio of our algorithms, and lower bounds on the competitive
      ratio of all online algorithms.