Invited Session Tue.2.MA 041

Tuesday, 13:15 - 14:45 h, Room: MA 041

Cluster 1: Approximation & online algorithms [...]

Practical implementations and models using approximation algorithms


Chair: David Phillips



Tuesday, 13:15 - 13:40 h, Room: MA 041, Talk 1

Rodrigo A. Carrasco
Experimental results of approximation algorithms for energy aware scheduling

Coauthors: Garud Iyengar, Cliff Stein


The increasing awareness of the environmental impact of massive data centres has led to an increased interest in energy management algorithms.
We have developed several new constant factor approximation algorithms for energy aware scheduling problems. The objective is to minimize the sum of the total energy consumed and the total weighted completion time or the total weighted tardiness in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and also release dates for the weighted completion time. Unlike previous known algorithms our new algorithms can handle general job-dependent energy cost functions extending their application to settings that have maintenance costs, wear and tear, replacement costs, etc., which in general also depend on the particular job being processed.
In this works we seek to understand the practical performance of these algorithms. We show that the practical performance is significantly superior to the theoretical bounds and in fact are very close to optimal. Additionally, we present heuristic improvements and we also investigate their performance in other settings: online, total weighted flow time, multiple machines, etc.



Tuesday, 13:45 - 14:10 h, Room: MA 041, Talk 2

Eyjolfur Ingi Asgeirsson
Performance of distributed game theoretic algorithms for single slot scheduling in wireless networks

Coauthor: Pradipta Mitra


We consider the capacity problem in wireless networks where the goal is to maximize the number of successful connections in arbitrary wireless networks where a transmission is successful only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. We study a game theoretic approach towards capacity maximization introduced by Andrews and Dinitz, where the key to the approximation is the use of low-regret algorithms. We prove vastly improved bounds for the game theoretic algorithm. In doing so, we achieve the first distributed constant factor approximation algorithm for capacity maximization for the uniform power assignment. When compared to the optimum where links may use an arbitrary power assignment, we prove a O(log Δ) approximation, where Δ is the ratio between the largest and the smallest link in the network. This is an exponential improvement of the approximation factor compared to existing results for distributed algorithms. All our results work for links located in any metric space. In addition, we provide simulation studies clarifying the picture on distributed algorithms for capacity maximization.



Tuesday, 14:15 - 14:40 h, Room: MA 041, Talk 3

David Phillips
Scheduling and planning magnetic resonance imaging machines

Coauthors: Adam Carpenter, Lawrence Leemis, Alan Papir, Grace Phillips


We devise models and algorithms to estimate the impact of current and future patient demand for examinations on magnetic resonance imaging (MRI) machines at a hospital radiology department. Our work helps improve scheduling decisions and supports MRI machine personnel and equipment planning decisions. Of particular novelty is our use of approximation algorithms from scheduling to compute the competing objectives of maximizing examination throughput and patient-magnet utilization. We also use resource augmentation to show that our algorithm is a O(1)-speed algorithm for computing a bicriteria solution. We present computational results demonstrating how our model can be used to both assess scheduling decisions as well as help guide planning decisions.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Buy Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.