ACLab is pleased to announce that Jhoirene Clemente has completed all her requirements for the degree of Doctor of Philosophy in Computer Science. Jhoirene will receive a doctorate from the College of Engineering, University of the Philippines Diliman (Department of Computer Science).


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

30 Sept 2019

Oral Defense of the Dissertation of



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

For the degree of




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





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


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.

13 September 2019

All are invited to the following:

Theory Days 2019


Theory Days 2019 celebrates two main reasons: 12 years of Algorithms and Complexity Laboratory at the Department of Computer Science in UP Diliman, as well as 107 years since the birth of Alan Turing. Theory Days 2019 aims to celebrate both these reasons by providing invited talks under the general theme of discrete mathematics and theoretical computer science and their related practice.

Talks and other activities in Theory Days 2019, such as brainstorming or break-out sessions, are largely informal in nature: the main reason is to initiate discussions which may lead to (in)formal collaborations, conference or journal articles, open problems for (under)graduate students and the computing community, or just for fun!


24 to 25 June 2019, 9AM to 5PM, ERDT room, 2nd floor, Alumni Engineers Centennial Hall, College of Engineering, UP Diliman, Quezon city.

Web page:

More details here: http://aclab.dcs.upd.edu.ph/productions/workshops/theorydays-2019