1. Applications and complexity of greedy algorithms in optimisation and mechanism design
- Author
-
Zhi, N., Krysta, Piotr, and Payne, Terry
- Subjects
004 - Abstract
This thesis studies one of the most classical algorithmic optimisation paradigms, which is the greedy paradigm. One of the main motivations for this thesis is to explore further applications of the greedy paradigm and to provide foundation for the mathematical analysis of the resulting greedy algorithms. We present a novel mechanism design model in the area of ontology alignment and study greedy mechanisms for this model. In particular, we provide bounds on the approximation ratios of truthful mechanisms in our model. Then we study the price of anarchy and that of stability of Nash implementations of greedy mechanisms. This study shows that the greedy paradigm provides a fast, practical and efficient mechanism. We then study the computational complexity and approximability properties of the greedy algorithm for the classic optimisation problem of computing maximum size independent sets in bounded degree graphs. We develop a series of novel methods to design advice for the greedy algorithm together with novel mathematical techniques of analysing the approximation performance of the resulting greedy algorithms. These techniques allow us to successfully design and prove the approximation ratios of the best known greedy algorithm for maximum size independent sets on sub-cubic graph, by designing a scheme to use savings to precisely pay for the greedy solution as compared to the optimal independent set. This scheme is highly non-local and it requires a complex inductive argument which we provide. We apply these methods also to the maximum size independent set problem on general bounded degree graphs and obtain near tight results. The maximum size independent set problem and the minimum size vertex cover problem are the two, mutually complementary, generic combinatorial optimisation problems. We apply our techniques also to the minimum size vertex cover problem and obtain improvements compared to previous results. Thus our techniques have a great potential for further applications of analysing greedy on other classes of graphs and for related optimisation problems. Interestingly, our theoretical analysis has been informed and advised by an experimental analysis which is also presented in the thesis. Finally, we also present an experimental analysis of our greedy algorithms. This thesis studies one of the most classical algorithmic optimisation paradigms, which is the greedy paradigm. One of the main motivations for this thesis is to explore further applications of the greedy paradigm and to provide foundation for the mathematical analysis of the resulting greedy algorithms. We present a novel mechanism design model in the area of ontology alignment and study greedy mechanisms for this model. In particular, we provide bounds on the approximation ratios of truthful mechanisms in our model. Then we study the price of anarchy and that of stability of Nash implementations of greedy mechanisms. This study shows that the greedy paradigm provides a fast, practical and efficient mechanism. We then study the computational complexity and approximability properties of the greedy algorithm for the classic optimisation problem of computing maximum size independent sets in bounded degree graphs. We develop a series of novel methods to design advice for the greedy algorithm together with novel mathematical techniques of analysing the approximation performance of the resulting greedy algorithms. These techniques allow us to successfully design and prove the approximation ratios of the best known greedy algorithm for maximum size independent sets on sub-cubic graph, by designing a scheme to use savings to precisely pay for the greedy solution as compared to the optimal independent set. This scheme is highly non-local and it requires a complex inductive argument which we provide. We apply these methods also to the maximum size independent set problem on general bounded degree graphs and obtain near tight results. The maximum size independent set problem and the minimum size vertex cover problem are the two, mutually complementary, generic combinatorial optimisation problems. We apply our techniques also to the minimum size vertex cover problem and obtain improvements compared to previous results. Thus our techniques have a great potential for further applications of analysing greedy on other classes of graphs and for related optimisation problems. Interestingly, our theoretical analysis has been informed and advised by an experimental analysis which is also presented in the thesis. Finally, we also present an experimental analysis of our greedy algorithms.
- Published
- 2019
- Full Text
- View/download PDF