Keynote Speakers
Speaker: Dr. Kazuo Iwama (Kyoto University, Japan)
Email: iwama@kuis.kyoto-u.ac.jp
Title: Narrowing (Already) Small Complexity Gaps
Date: 2017-12-16
Abstract: Suppose that some problem has an algorithm which runs in time \(O(n)\). This algorithm is optimal in the usual sense and there is little room for further improvements. One may be interested in the constant factor that is hidden by the big-O notation, but that would cause nasty issues about machine models. On the other hand, there are several other complexity measures that are more accurate and cleaner than the number of computation steps. One of them is the number of comparisons for evaluating sorting algorithms. In many textbooks, it is just written that fast algorithms need \(O(n\log n)\) comparisons (log means the logarithm of base \(2\) here) which is optimal. It turns out, however, that its information theoretic lower bound is \(\log(n!)\), which is approximately equal to \(nlogn-1.4426n+O(\log n)\). For instance, it is easy to prove that the simple binary insertion sort needs at most nlogn comparisons, but it is much harder to specifically bound the linear term or to bound its constant factor. The current best upper bound for that constant factor is \(-1.32\) due to Ford and Johnson that is published in 1959! Another example of such measure is the number of oracle calls for reconstruction of strings which is a model of sequence by hybridization. Again the current upper bound is \(n+2\log n\) and it was a long-standing open question whether the logn term can be removed. This talk is about our two recent results on improved upper bounds for those complexity measures. Such a small improvement may be useless in practice, but it needs a lot of new algorithmic techniques that may be useful in other occasions. Even more importantly, those are nice examples to demonstrate the power of randomization and/or the advantage of the average-case complexity over the worst-case complexity.
Biography: Professor Iwama received B.E., M.E. and Ph.D. degrees from Department of Electrical Engineering, Kyoto University in 1973, 1975 and 1980, respectively. He is the project professor of Kyoto University, and his research interests are mainly algorithms and complexity theory. He is the member of Academia Europae, the editor-in-chief of European Association for Theoretical Computer Science (EATCS), and the founder and president of Asian Association for Algorithms and Computation (AAAC). He was also the organizing committee chair of ICALP/LICS 2015 and 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012). Prof. Iwama had published more than 200 papers. He was also the Honorary Doctorate of University of Latvia.
Speaker: Dr. Ding-Zhu Du (University of Texas at Dallas, USA)
Email: dzdu@utdallas.edu
Titile: Maximization of Multi-Factor Influence
Date: 2017-12-17
Abstract: In viral marketing, a customer gets influenced usually by not only a single factor, but also more than one factors, or multiple factors. For example, both quality and price of a product are very important for a customer to make his decision on buying or not. In this talk, we consider a model with following properties: (a) A product is described by \(k\) (\(k \geq 2\)) factors and a customer buys the product if and only if he gets influenced on every factor. (b) All factors are independent so that influence diffusion of each factor follows an independent cascade model in the networks and different factors may follows different independent cascade models, that is, accepting probabilities for different factors on each edge may be different. Of course, the maximization of influence spread is NP-hard. We show that the influence spread in this model is still a submodular function and hence its maximization has a \((1-1/e)\)-approximation.
Biography: Dingzhu Du received the Ph.D. degree from the University of California, Santa Barbara, in 1985. He was a post doctor of the institute of mathematical science of University of California, Berkeley during 1985~1986. After that he went to the department of mathematics of MIT at 1986 as a visiting scholar. In 1987 he left MIT and took the position as a professor at institute of mathematics of Chinese Academy of Sciences. He became an associate professor and then the professor at the department of computer science of the University of Minnesota from 1991 to 1995. Currently he is the professor of the department of computer science of University of Texas at Dallas and the project supervisor of the computer theoretics of the NSF committee. Dr. Du had published more than 200 paper on the top conference of computer science and journals, and more than 10 authored books. He is the chief editor of the network theory and application, and editorial board member of more than 15 journals. He received CSTS award from INFORMS in 1998, the 2nd class prize of the Chinese NSF in 1993 and the 1st class prize of natural science of Chinese Academy of Sciences.
Speaker: Dr. Simai He (Shanghai University of Finance and Economics, China)
Email: simaihe@mail.shufe.edu.cn
Titile: A Non-Asymptotic Approach to Analyze Kidney Exchange Graphs
Date: 2017-12-17
Biography: Simai He is a professor in Department of Management Science, Shanghai University of Finance and Economics. His research focuses on optimization, game theory and supply chain management. He published papers in OR and CS journals and conferences such as Operations Research, Mathematics of Operations Research, Mathematical Programming, SIAM Journal on Optimization, FOCS, SODA and EC. He won Gold Medal in 33rd International Mathematical Competition. He also received the Award for Young Scientists from the Operations Research Society of China in 2014. He has been widely consulting for companies such as JD, Didi and NetEase, etc, and is the Chief Scientist of Cardinal Operations.
Abstract: We propose a novel methodology to study kidney exchange. Taking the random graph model of kidney exchange introduced in Ashlagi, Garmarnik, Rees and Roth's "The need for (long) chains in kidney exchange" (2012), we propose a non-asymptotic approach to quantifying the effectiveness of transplant chains in reducing the number of unmatched highly sensitized patients. Our approach is based on a two phase random walk procedure where random walks are used to allocate chains, followed by allocation via matching in cycles. The benefit of random walks is that they preserve the probabilistic structure of residual graphs, greatly facilitating analysis. The approach allows us to analytically show the benefit of chains, as compared to transplantation in two-way cycles only, in non-asymptotic (medium-sized) graphs. We also derive useful analytical bounds that illustrate the performance of our proposed allocation procedure and more general kidney allocation procedures. Our results complement previous findings on the benefits of chains that includes analytical results in large (limit) graphs and empirical results based on data from fielded kidney exchanges.