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
Abstract
Unless P=NP, we cannot obtain a polynomialtime 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 approximable, i.e., we can obtain a polynomialtime 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 polynomialtime approximation
scheme (PTAS) for a reoptimization variant of a problem given that the unmodified problem is approximable.
REFERENCES:
[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.
[8] V. Vazirani, Approximation Algorithms, vol. 94. 2001, p. xx+378.


