Algorithm design for min-energy voltage allocation and incentive compatible tournament selection protocol


Student thesis: Master's Thesis

View graph of relations


  • Jie LIU

Related Research Unit(s)


Awarding Institution
  • Frances Foong YAO (Supervisor)
  • Xiaotie DENG (Co-supervisor)
Award date15 Feb 2006


This thesis addresses two algorithm design problems. The first problem focuses on how to efficiently produce optimal schedules for a set of jobs running on variable voltage processors. The second problem is concerned with the existence of ideal tournament protocols that can prevent players from cheating. Both problems deal with important issues in the field of combinatorial algo- rithms. Optimal scheduling on variable voltage processors has been studied exten- sively over the years, especially after portable electronic devices become more and more common in daily life. The tournament design problem is a newly proposed problem for which only a few related studies exist. In the first part, we study job scheduling on dynamic processors to minimize energy consumption, under the assumption that the processors are capable of run- ning at variable continuous voltages/speeds. Each job in a problem instance is specified by its arrival time, deadline, and required number of CPU cycles. The minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree’s total path length. We also study an on-line average-rate heuristics (AVR) and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlaps. Some simulation results are also given. In the second part, we consider the incentive compatible mechanism design for the problem of selecting m highest ranked players out of n candidates through pairwise comparisons. Deviating from the standard model, it is assumed that the outcome of a pairwise comparison may be manipulated by the two participants, i.e. bad players. The higher ranked party may intentionally lose to the lower ranked party in order to gain group benefit. The problem is studied under two models. Under both models, a coalition will try to have more players of their group to be selected as winners than to be chosen according to their true ranking. Under the collective incentive compatible model, where players fight for group benefit at all cost, we prove the inexistence of ideal protocol for general case. Under the alliance incentive compatible model, where all players ought to win remain winners, we prove the inexistence of ideal protocols when n−m ≤ 2, and presented an incentive compatible protocol for the case n − m ≥ 3

    Research areas

  • Systems on a chip, Power supply, Microprocessors