Cyclic Schedules and the LP Formulation

For more info about our services contact : help@bestpfe.com

Table of contents

1 Introduction 
1.1 Online Computation
1.1.1 Competitive Analysis
1.1.2 Techniques in Design and Analysis of Online Algorithms
1.2 Online Computation with Recourse
1.2.1 Online Matching with Recourse
1.3 Other Performance Measures
1.3.1 The Linear Search Problem
1.3.2 The Discovery Ratio
1.3.3 An Application from Artificial Intelligence
1.4 Online Computation with Advice
1.4.1 A New Model with Untrusted Advice
1.4.2 Online Bidding with Untrusted Advice
1.5 Summary of the Thesis
2 Online Maximum Matching with Recourse 
2.1 Introduction
2.1.1 RelatedWork
2.1.2 Contributions
2.1.3 Preliminaries
2.2 Online matching in the edge arrival model
2.2.1 The Algorithm AMP
2.2.2 The Algorithm GREEDY
2.2.3 The algorithm L-GREEDY
2.2.4 Lower Bound on the Competitive Ratio of Deterministic Algorithms
2.2.5 Comparing the Algorithms L-GREEDY and AMP
2.3 Online Matching in the Edge Arrival/Departure Model
2.4 Conclusion
3 Searching on the Line Using Discovery Ratio 
3.1 Introduction
3.1.1 RelatedWork
3.1.2 Contribution
3.1.3 Preliminaries
3.2 Strategies of Optimal Discovery Ratio in S
3.3 The Discovery Ratio of Competitively Optimal Strategies
3.3.1 Properties of Competitively Optimal Strategies
3.3.2 Discovery Ratio of Strategies in S9
3.3.3 On the Uniqueness of Strategies with Optimal Discovery Ratio
3.4 Computational Evaluation
3.5 Conclusion
4 Contract Scheduling with End Guarantees 
4.1 Introduction
4.1.1 Contribution
4.1.2 Preliminaries
4.2 Cyclic Schedules and the LP Formulation
4.3 Obtaining an Optimal Schedule
4.4 Computational Evaluation
4.5 Conclusion
5 Online Bidding with Untrusted Advice 
5.1 Introduction
5.1.1 Online Computation with Advice
5.1.2 A New Model with Untrusted Advice
5.1.3 Online Bidding with Untrusted Advice
5.1.4 Preliminaries
5.2 Identifying a Pareto-optimal Bidding Strategy
5.2.1 Algorithm Overview
5.2.2 Phase 1: Identifying a dominant strategy X m ,u in Sm,u
5.2.3 Phase 2: Identifying an optimal strategy X u
5.3 Conclusion
6 Conclusion
6.1 Summary of Results
6.2 What Next ?