Global ETD Search

1	Techniques for Proving Approximation Ratios in Scheduling Ravi, Peruvemba Sundaram January 2010 (has links) The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture. Approximation Ratios Scheduling Makespan Flowtime-optimal Schedules Coffman-Sethi Conjecture LD Algorithm Combinatorics and Optimization
2	Techniques for Proving Approximation Ratios in Scheduling Ravi, Peruvemba Sundaram January 2010 (has links) The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture. Approximation Ratios Scheduling Makespan Flowtime-optimal Schedules Coffman-Sethi Conjecture LD Algorithm Combinatorics and Optimization
3	Essays on Mathematical Economics Ninjbat, Uuganbaatar January 2012 (has links) <p>Diss. Stockholm : Stockholm School of Economics, 2012. Introduction together with 6 papers</p> Optimal schedules FCFS The Leontief preferences Approval voting Young's theorem May's theorem Strategy-proofness Options sets Impossibility theorem Economics Nationalekonomi
4	Estimation over heterogeneous sensor networks Sandberg, Henrik, Rabi, Maben, Skoglund, Mikael, Johansson, Karl Henrik January 2008 (has links) Design trade-offs between estimation performance, processing delay and communication cost for a sensor scheduling problem is discussed. We consider a heterogeneous sensor network with two types of sensors: the first type has low-quality measurements, small processing delay and a light communication cost, while the second type is of high quality, but imposes a large processing delay and a high communication cost. Such a heterogeneous sensor network is common in applications, where for instance in a localization system the poor sensor can be an ultrasound sensor while the more powerful sensor can be a camera. Using a time-periodic Kalman filter, we show how one can find an optimal schedule of the sensor communication. One can significantly improve estimation quality by only using the expensive sensor rarely. We also demonstrate how simple sensor switching rules based on the Riccati equation drives the filter into a stable time-periodic Kalman filter. ï¿œ 2008 IEEE. / <p>QC 20110224</p> Communication costs Design trade-offs Estimation performance Estimation qualities Heterogeneous sensor networks High qualities Localization systems Low qualities Optimal schedules Processing delays Sensor communications Sensor scheduling Stable time Switching rules Ultrasound sensors Communication Control theory Estimation Heterogeneous networks Kalman filters Riccati equations Sensor networks Computer science Datavetenskap

1

Page generated in 0.0606 seconds