Invited Speakers

Invited Speakers:

Structural Properties of Hard Problem Instances

Tobias Moemke, Ph.D.

Researcher

Theoretical Computer Science

School of Computer Science and Communication

Royal Institute of Technology

Stockholm

Abstract

Most of the hardness results for NP-hard problems are derived for worst-case scenarios and in many cases it is not clear whether the actual problem instances arising in practical applications exhibit this worst-case behavior. A recent branch of algorithmic research aims at a more fine-grained analysis of the hardness of optimization problems. The main idea behind this analysis is to find some parameter according to which one can classify the hardness of problem instances. In this spirit, we characterize instances for the metric TSP according to the solution computed by Hoogeveen's 5/3-approximation algorithm for the problem to find a Hamiltonian path with prespecified ends in the same metric graph. Our analysis reveals that the sets of the hardest instances of both problems for Christofides' and Hoogeveen's algorithm are disjoint in the sense that any instance is guaranteed to allow at least one of the two algorithms to achieve a significantly improved approximation ratio. In particular, any input instance that leads to a $5/3$-approximation with Hoogeveen's algorithm enables us to find an optimal solution for the traveling salesman problem.

Mathematical Concepts in Digital Image Processing and Their Real-World Applications

Vladimir Mariano, Ph.D.

Associate Professor, Director

Institute of Computer Science

University of the Philippines Los Banos

Laguna

Abstract

Mathematics is the foundation of every image processing method. Everything from image warping, filtering, shape representation, color analysis, to video analysis has a mathematical basis. In this talk, several mathematical concepts will be presented and connected to real-world projects in image processing.

Bioinformatics Research at Ateneo de Naga

Allan Sioson, Ph.D.

Professor of Computer Science

Ateneo De Naga University

Naga City, Bicol

Biodata management and Simulation are two main aspects of Bioinformatics work in Ateneo de Naga University. In this talk, I present the progress we are making in managing the wealth of diverse biological data of species in Mt. Isarog Natural Park, generation of simulated microarray data, and gene regulation network simulation.

Organizers