Theory Day in Taiwan (2017B)

Lusheng Wang

Title: Algorithms for Pedigree comparison and closest string problems

---

Abstract: In this talk we will discuss some recent progress pedigree comparison and closest string problems. We introduce three models for comparison of pedigrees, the maximum pedigree isomorphism problem, the maximum paternal-path-preserved mapping problem and the minimum edge-cutting mapping problem. Exact and fixed-parameter algorithms are given for different cases. For the closest string problem, we will present a new fixed parameter algorithm with running time O(n26.16d).

Bio:
Lusheng Wang got his Ph.D degree from MacMaster University in 1995. He joined City University of Hong Kong in 1996. He is now a professor at City University. His research interests include algorithms, computational biology and bioinformatics. He is current an associate editor for Journal of Computer and System Sciences, IEEE/ACM Trans. on Computational Biology and Bioinformatics, and BMC Bioinformatics.

Wing-Kai Hon

Title: Stabbing Colors in One Dimension

---

Abstract: Given n horizontal segments, each associated with a color from [1,s], the Categorical Segment Stabbing problem is to find the distinct K colors stabbed by a vertical line. When the endpoints of the segments are distinct and lie in [1, 2n], we present an (2 + eps ) n log s + O(n)-bit index with O(K/eps ) query time, where 0 < eps <= 1. When the endpoints are arbitrary real numbers, a standard reduction to the above scenario improves the existing bounds of Janardan and Lopez. We also present results for few other variations:
1. reporting the top-k colors that are stabbed, where each color has a fixed priority.
2. handling these scenarios when the given segments form a tree range.

This is a joint work with Arnab Ganguly (LSU) and Rahul Shah (LSU & NSF).

Bio:
Wing-Kai Hon obtained his PhD degree in 2005 from the University of Hong Kong, under the guidance of Tak-Wah Lam. During 2004--2006, he visited Purdue University as a post-doc under the supervision of Jeff Vitter. He joined National Tsing Hua University, Taiwan, in August 2006, and is now an associate professor in the Department of Computer Science. His research interests include indexing, data compression, external memory data structures, and combinatorial optimization.

Naoki Katoh

Title: Mathematical Model and Algorithms for Quickest Evacuation Planning

---

Abstract: In recent years, catastrophic disasters by massive natural disasters such as typhoon, earthquake, tsunami, volcano eruption have been increasing in the world, and disaster management is becoming extremely important more than ever. For example, in the Tohoku-Pacific Ocean Earthquake that happened in Japan on March 11, 2011, serious damage was caused by a tsunami. Although disaster prevention in civil and architectural engineering fields in Japan has been considered previously mainly from physical aspects, it is difficult to prevent large tsunamis physically. Therefore, disaster prevention from non-physical aspects, such as city planning and evacuation planning, has become more important recently.

A mathematical approach is useful in finding an effective evacuation planning. The evacuation planning can be formulated based on network flow, and we have proposed an evacuation model to find the fastest time for complete evacuation of evacuees. Developing a practically efficient algorithm for computing quickest flows is a still challenging problem although the existence of a polynomial time algorithm was shown by Hoppe and Tardos more than fifteen years ago. Also, the problem of finding an optimal location of evacuation sites has recently been studied where there still remain theoretically interesting problems.

In this talk, we shall explain how evacuation planning is modeled as a mathematical programming problem, and algorithmic issues. We shall also explain several cases where we applied network flow model to find quickest evacuation planning.

Bio:
Naoki Katoh is currently a professor at School of Informatics in Kwansei Gakuin University. His research interests include the design and analysis of combinatorial and geometric algorithms. In particular, his research interests are focusing on combinatorial rigidity theory and evacuation planning problems. He is currently a Research Director of JST-CREST for Innovative Algorithms for Big Data.

He published more than 140 journal papers and more than 100 international conference papers. He also published a book, The Resource Allocation Problems: Algorithmic Approaches; from MIT Press, in 1988. In 2000, he received Hao Wang Award.

Kunihiko Sadakane

Title: Succinct Data Structures: Theory and Practice

---

Abstract: Succinct data structures are data structures that can compress data to the limit and perform search and other operations quickly without decompressing the data. In this talk, the basic theory and applications of succinct data structures are explained.

Bio:
Kunihiko SADAKANE received Ph.D. degree from The University of Tokyo in 2000. He was a research associate at Tohoku University from 2000, an associate professor at Kyushu University from 2003, an associate professor at National Institute of Informatics from 2009. Since 2014, he has been a professor at Graduate School of Information Science and Technology, The University of Tokyo. His research interest includes information retrieval, data structures, and data compression.