30 Sept 2019

Oral Defense of the Dissertation of

JHOIRENE BARASI CLEMENTE

entitled

Additional Information in Computation: Reoptimization and Advice for Some Combinatorial Problems

For the degree of

DOCTOR OF PHILOSOPHY

(COMPUTER SCIENCE)

on

30 SEPT 2020, 4:00 PM - 7:00 PM (Manila Time)

ERDT ROOM 

UP ALUMNI ENGINEERS CENTENNIAL HALL

UP DILIMAN, QUEZON CITY

________________

Panel Members

Dr. Henry N. Adorna, Adviser

Dr. Jaime DL. Caro, Panel Chairman

Dr. Proceso Fernadez, Reader

Dr. Eugen Rex Jalao, Panel Member

Dr. Prospero Naval, Panel Member

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 reoptsk, reoptpk, and reoptmk, 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 ltn ((t-r) choose r) and $ t(n-(l+k)+1){t(l+2k) \choose r}$ steps for reoptsk and reoptpk, respectively. 

In the context of advice, we investigate the ONLINE-SEARCH (OS) problem and its generalization, the  ONLINE K-SEARCH (OkS).  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  OS and OkS, online algorithm with advice overpowers the best possible deterministic and randomized online algorithms in terms of competitiveness.