Status : Deleted
| Personal Name | Clemente, Jhoirene |
|---|---|
| Resource Title | Additional information in computation: reoptimization and advice for some combinatorial problems |
| Date Issued | 20 November 2019 |
| Abstract | In the last few decades, technological advancements in computing have proliferated. These advancements allow faster data processing and storage on a very large scale. Information is now cheaper than ever. In this study, we investigate how information is beneficial to computation in the context of reoptimization and advice. Reoptimization is a combinatorial setting applied to NP-hard optimization (NPO) problems and advice is a piece of information provided by an oracle to an online algorithm to compensate for not knowing the whole input instance. In reoptimization, an optimal solution to a locally modified version of the problem is given in advanced. We investigate how reoptimization can be beneficial in solving the consensus pattern problem (CPP). We show that for the variants CPPM(t+k), CPPM(l+k), and CPPM(l−k), additional information does not help in reducing the hardness of the problem. We then show that one can use the given optimal solution to provide an approximate solution for the new input instances of these variants and we identify the conditions in which it is beneficial to use this information as compared to solving the problem from scratch. We also show that by using the additional information in reoptimization, we can improve the running time of the existing polynomial-time approximation scheme (PTAS) for CPP while maintaining the solution quality guarantee. Computation is reduced by tlnC(t-r, r) and t(n-(l+k)+1)C(t(l+2k),r) steps for CPP-M(t+k) and CPP-M(l+k), respectively. In the context of advice, we investigate the Online Search problem and its variants Online k-Search and One-Way Trading. We show the minimum amount of advice necessary to achieve optimality of any online algorithm. We show upper bound and lower bound limits of any algorithm achieving certain competitive ratios given less advice. We show that in the case of Online Search and Online k-Search, online algorithm with advice overpowers the best possible deterministic and randomized online algorithms in terms of competitiveness. |
| Degree Course | PhD Computer Science |
| Language | English |
| Keyword | advice complexity; approximation; combinatorial optimization; online algorithms; reoptimization |
| Material Type | Thesis/Dissertation |