Welcome to visit Chung-Shou Liao’s lab! Our research mainly focuses on designing efficient combinatorial algorithms that can be used to solve hard optimization problems from real applications. We are interested in developing approximation algorithms with theoretical analysis for network and location problems such as online shortest path, facility location, scheduling and packing problems and so on. Other areas of interest include computational geometry, graph theory, and machine learning. In particular, we also extend to systems biology for global alignment between multiple biological networks. In recent years, we put more attention on dynamic and online algorithms for the fundamental problems such as data clustering and classification, as well as their applications to AI manufacturing.

Honors and Award News

2019.01.  Our lab receives the funding support of the MOST 4-year AI project.
2018.12.  Our lab finishes organizing the 29th ISAAC in Jiaoxi, Yilan, Taiwan on Dec. 16 to 19, 2018.
2018.07.  Our PI receives 2018 Young Scholar Creativity Award, Foundation for the Advancement of Outstanding Scholarship.
2018.06.  Hao-Ting Wei’s paper, entitled An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity, has been accepted by APPROX 2018 .
2017.12.  Our PI is nominated to be Fulbright Senior Research Scholar in 2018 & 2019.

Academic Service (Selected)

PC Chair: ISAAC 2018, AAAC 2016
Associate Editor: Journal of Combinatorial Optimization
Board Member: AAAC (Asian Association for Algorithms and Computation)
Secretary General: AACT (Association for Algorithms and Computation Theory, Taiwan)

Intelligent Manufacturing

This AI project on smart manufacturing would like to investigate practical problems and challenges derived from our recent industrial collaboration with high-tech manufacturing companies. Although there were some manufacturing process problems that can be overcome by conventional machine learning approaches, these problems, however, have good-to-use properties or easy-to-retrieve features. As the high-tech manufacturing process “has been getting increasingly complicated, the “key” processes have become a serious challenge for most of the high-tech manufacturing companies.”We first take into consideration the lithography process in the semiconductor industry as the short-term goal to elaborate the artificial intelligence optimization applications. Apart from most advanced process control systems that used statistical measured data, we further attempt to make use of real data visualization. Next, we define the associated clusters from big data and conduct automatic compensation through deep learning approaches with artificial intelligence. We extend to some other processes under the mechanism of big data analysis as well as AI optimization applications so that the settings of these processes are no longer independent of each other. We even further exploit similar techniques in other high-tech manufacturing industries.In particular, this project receives the great support from semiconductor companies which promise to provide their data centers for our study. We also collaborate with our partner laboratories to develop compression techniques for deep neural network learning models, which can accelerate the learning and inference steps in deep learning. Moreover, based on the concept of Collective Intelligence, we study and build knowledge cases through multi-channel sources. Finally, we will establish a platform for knowledge management and decision support. The ultimate goal of this project aims to construct an Advanced Process Control and Decision Making Platform through big data mining and artificial intelligence techniques for high-tech manufacturing industries.(more details)

Online Route Planning on Road Networks

Modern technologies such as Global Positioning Systems (GPS) and mobile communication have contributed to the development of dynamic navigation planning based on real-time information. However, traffic conditions vary enormously and unpredictable accidents significantly affect planned routes, which increase the problem complexity, even though current navigation systems use information about road distances and speed limits to find the fastest routes. Therefore, online decision-making strategies play an important role in solving traffic congestion problems. We consider an old online route planning problem, called the Canadian Traveller Problem (CTP), which finds practical applications in designing dynamic navigation systems. We study several generalizations of the CTP and propose deterministic algorithms with theoretical competitive ratio. We also present the first polynomial time randomized algorithm that surpasses the deterministic lower bound. Recently, we consider the electric vehicle (EV) routing problem that takes into consideration of possible battery charging or swapping operations. We develop efficient algorithms which can be implemented on an online EV routing map interface (more details).

Biological Network Alignment

A fundamental goal of biology is to understand the cell as a system of interacting components and especially, almost every biological process is mediated by a network of molecular interactions. In particular, there has been a considerable amount of research devoted to the discovery and exploration of interactions between proteins in the last decade. Since many cellular activities are a result of protein interactions, proteins often interact with other proteins to perform their functions, and form a complex biological system, i.e., a protein-protein interaction (PPI) network. This powerful way of representing and analyzing the vast corpus of PPI data describes the interaction relationship among proteins in a cell. Furthermore, knowledge about the topology of a PPI network in one organism can yield insights about not only the networks of similar organisms, but also the function of their components. Hence comparison between protein interaction networks is becoming central to systems biology. We have collaborated with the MIT team and developed global alignment algorithms for performing comparative analysis of multiple biological networks (more details).

Power Observation on Grids

When the global energy crisis and related issues become critically important, more researchers focus on the energy management problems and especially, Smart Grid is one of the most popular research topics. In order to solve the technical challenges of communications between power plants and stations, power companies have to observe the real-time state of a power grid and continually monitor the whole electricity system. The PMU (phasor measurement unit) was invented and such devices can measure the electrical waves on a power grid and determine the health of the utility system. We consider the power observation problem of optimally placing PMU devices on wide-area power grids according to different objectives, while maintaining the ability to observe electricity systems (more details).

Capacitated Facility Location

With the rapid growth of international logistics market, one of the most important research issues is designing a large-scale distribution network. The question of large-scale distribution network design is also becoming central to globalization supply chain management. In general, the location and network design problems have become more important and have been studied extensively during the last decade. In order to deal with different real-world applications in which the constraints and requirements appear in different scenarios, these problems can be formulated in various ways. We study capacitated facility location in large-scale networks and its application to distribution network design. In a distribution network, each distribution center or client has associated with a demand, and each plant or facility has a capacity that specifies the maximum service the plant can provide to its distribution centers. (more details).