Candidacy Lecture

posted Jul 23, 2014, 4:48 AM by Jhoirene Clemente   [ updated Oct 9, 2014, 2:42 AM ]

WHAT: Candidacy Lecture on Reoptimization Techniques for Solving Hard Problems
WHEN: July 30, 2014
WHERE: ERDT Room, UP Alumni Engineers Centennial Hall, UP Diliman

Unless P=NP, we cannot obtain a polynomial-time algorithm solving hard combinatorial problems. One practical approach in solving this kind of problem is to relax the condition of always finding the optimal solution for an
instance and settle for “good enough” solutions. The kind of algorithms which are guaranteed to obtain a solution with a certain quality are called approximative algorithms. However, not all hard problems are approximablei.e., we can obtain a polynomial-time algorithm that can guarantee the goodness of the solution for a problem. 

In this lecture, we will present the concept of reoptimization. In this approach, given an instance I of some problem Π, an optimal solution OPT for Π in I, and a modified instance I' resulting from a local perturbation of I, we wish to use
OPT in order to solve Π in I'. With this additional information, reoptimization may help to improve the approximability of the problem or the running time of the solution to it. In fact, we can obtain a polynomial-time approximation
scheme (PTAS) for a reoptimization variant of a problem given that the unmodified problem is approximable.


[1] G. Ausiello, V. Bonifaci, and B. Escoffier, “Complexity and approximation in reoptimization”, in Computability in Context:Computation and Logic in the Real World, vol. 2, 2011, pp. 101–129.

[2] D. Bilò, H. Böckenhauer, and D. Komm, “Reoptimization of the Shortest Common Superstring Problem”, Algorithmica, vol. 293, pp. 1–14, 2011.

[3] N. Boria, J. Monnot, and V. Paschos, “Reoptimization of maximum weight induced hereditary subgraph problems”, Theoretical Computer Science, pp. 1–12, 2012.

[4] J. H. T. M. P. W. Hans-joachim Böckenhauer, “On the hardness of reoptimization”,  Proc. 34th IIn Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), LNCS, vol. 4910, 2008.

[5] Juraj Hromkovic, “Algorithmics for Hard Problems”, ETH Zurich, 2001.

[7] H. Shachnai, G. Tamir, and T. Tamir, “A Theory and Algorithms for Combinatorial Reoptimization,” Lecture Notes Computer Science, vol. 7256, no. 1574, pp. 618–630, 2012.

[8] V. Vazirani, Approximation Algorithms, vol. 94. 2001, p. xx+378.

[9] A. Zych, “Reoptimization of NP-hard Problems”, ETH Zurich, Dissertation, 2012.