COCOON 2021

Title: Coupon Allocation in Social Market : Robust and Machine Learning

Speaker: Prof. Ding-Zhu Du, University of Texas at Dallas, USA

Date/Time: October 25, 2021 / 9:30 - 10:30 UTC+8

Abstract: In this talk, we consider the coupon allocation problem in marketing. It has been reported that 40% of consumers will share an email offer with their friend and 28% of consumers will share deals via social media platforms. What does this mean for a business? Essentially discounts should not just be treated as short term solutions to attract individual customer, instead, allocating coupon to a small fraction of users (called seed users) may trigger a large cascade in a social market. This motivates us to study the influence maximization coupon allocation problem: given a social network and budget, we need to decide to which initial set users should offer the coupon, and how much should the coupon be worth. Our goal is to maximize the number of customers who finally adopt the target product. The talk is based on recent research paper of Jianxiong Guo et al..

Bio: Ding-Zhu Du received his M.S. degree in 1982 from Institute of Applied Mathematics, Chinese Academy of Sciences, and his Ph.D. degree in 1985 from the University of California at Santa Barbara. He worked as a postdoctor at Mathematical Sciences Research Institute, Berkeley in 1985-86, as an assistant professor at MIT in 1986-87, and as a research associate at Princeton University in 1990-91. He was an associate-professor/professor at Department of Computer Science and Engineering, University of Minnesota in 1991-2005, a Program Director for Theory of Computing at National Science Foundation of USA in 2002-2005, and a research professor at Institute of Applied Mathematics, Chinese Academy of Sciences, in 1987-2002. Currently, he is a professor at Department of Computer Science, University of Texas at Dallas. His research interest is in theory of computation, especially in design and analysis of approximation algorithms for combinatorial optimization problems with applications in computer and communication networks, and social networks. He has published more than 230 journal papers and more than 10 books. He is the founder of Journal of Combinatorial Optimization and an co-Editor-in-Chief of Computational Social Network and Discrete Mathematics, Algorithms and Applications. He is also in editorial boards of more than 15 journals.

Title: Discrepancy Theory in Combinatorics, Geometry and Computation

Speaker: Prof. Takeshi Tokuyama, Kwansei Gakuin University, Japan

Date/Time: October 25, 2021 / 10:45 - 11:45 UTC+8

Abstract: Discrepancy theory investigates uniformity, and appears in several aspects of mathematics and computer science. Consider a range space consisting of a set of n points P in the unit square [0,1] x [0,1] (in general, d-dimensional unit cube) and a family R of subregions in the square. For a region R ∈ R with area Area(R), let D(P, R) = |n Area(R) - |P ∩ R| |. If P is ideally uniformly distributed, D(P, R) should be small for each R, and we define $D(P,{∈ R}) =sup_{R ∈ R} D(P, R). The geometric discrepancy of n points with respect to R is D(n, R) = inf_{P, |P|=n} D(P, R), which gives the limit of uniformity of point distribution with respect to R. A classical result is that D(n, R) = ⊖ logn if R is the set of all axis-parallel rectangular regions. There are some other related discrepancies defined on hypergraphs. In this talk, discrepancy theory and its applications including recent results on consistent digital curved rays will be discussed.

Bio: Takeshi Tokuyama received PhD in mathematics in 1985 from University of Tokyo. He worked as a research staff member of IBM Tokyo Research from 1986 to 1999, and as a professor and a dean of Graduate School of Information Sciences of Tohoku University from 1999 to 2019 and 2015 to 2018, respectively. Currently, he is a professor of Kwansei Gakuin University, Japan. He worked on theory of algorithms including computational geometry, combinatorial optimization and data mining/analysis, and was the chair of the advisory committee of ISAAC (International Symposium on Algorithms and Computation) from 2008 to 2017. He is a member of Science Council of Japan, and editors of DCG, CGTA, IJCGA, and JoCG.

Title: Learning Graphs with Topology Properties

Speaker: Prof. Tony Q.S. Quek, Singapore University of Technology and Design, Singapore

Date/Time: October 26, 2021 / 13:00 - 14:00 UTC+8

Abstract: Graphs are mathematical tools, consisting of nodes (vertices) and links (edges), used in various fields to represent, process, visualize, and analyze structured data. In many cases, datasets consist of an unstructured list of samples, and the underlying graph topology (representing the structural relations between samples) is unknown. It is thus desirable to learn the graph from data. Typically, graph learning is an ill-posed problem since multiple solutions may exist associating a graph with the data. In this talk, we show how constraints can be imposed directly on the learned graphs so as to enforce certain topology properties that can best fit the data. Specifically, inspired by a specific application domain (e.g., community detection), we develop a graph learning method that learns a graph with overlapping community structure. Our method encompasses and leverages the community structure information, along with attributes such as sparsity and signal smoothness to capture the intrinsic relationships between data entities, such that the estimated graph can optimally fit the data. Furthermore, we extend to more complex datasets with heterogeneous graph signals. In summary, our methods can incorporate topology properties in graph learning, which makes it possible to capture complex and non-typical behavior of graph signals that cannot be explicitly handled just by observed data.

Bio: Tony Q.S. Quek received the B.E. and M.E. degrees in Electrical and Electronics Engineering from Tokyo Institute of Technology, Tokyo, Japan, respectively. At Massachusetts Institute of Technology (MIT), Cambridge, MA, he earned the Ph.D. in Electrical Engineering and Computer Science. Currently, he is the Cheng Tsang Man Chair Professor with Singapore University of Technology and Design (SUTD) and the Visiting Chair Professor with CSIE at NCKU. He also serves as the Head of ISTD Pillar, Sector Lead for SUTD AI Program, and the Deputy Director of SUTD-ZJU IDEA. His current research topics include wireless communications and networking, big data processing, network intelligence, URLLC, and IoT.
Dr. Quek has been actively involved in organizing and chairing sessions and has served as a TPC member in numerous international conferences. He is currently serving as an Editor for the IEEE Transactions on Wireless Communications and an elected member of the IEEE Signal Processing Society SPCOM Technical Committee. He was an Executive Editorial Committee Member of the IEEE Transactions on Wireless Communications, an Editor of the IEEE Transactions on Communications, and an Editor of the IEEE Wireless Communications Letters. He is a co-author of a few books published by Cambridge University Press.
Dr. Quek received the 2008 Philip Yeo Prize for Outstanding Achievement in Research, the 2012 IEEE William R. Bennett Prize, the 2016 IEEE Signal Processing Society Young Author Best Paper Award, the 2017 CTTC Early Achievement Award, the 2017 IEEE ComSoc AP Outstanding Paper Award, the 2020 IEEE Communications Society Young Author Best Paper Award, the 2020 IEEE Stephen O. Rice Prize, the 2020 Nokia Visiting Professorship, and the 2016-2020 Clarivate Analytics Highly Cited Researcher. He is a Distinguished Lecturer of the IEEE Communications Society and a Fellow of IEEE.

Title: Bamboo Garden Trimming Problem (Perpetual maintenance of machines with different urgency requirements)

Speaker: Prof. Ralf Klasing, CNRS and University of Bordeaux, France

Date/Time: October 26, 2021 / 14:00 - 15:00 UTC+8

Abstract: A garden G is populated by n >= 1 bamboos b_1, b_2, ..., b_n with the respective daily growth rates h_1 >= h_2 >= ... >= h_n. It is assumed that the initial heights of bamboos are zero. The robotic gardener maintaining the garden regularly attends bamboos and trims them to height zero according to some schedule. The Bamboo Garden Trimming Problem (BGT) is to design a perpetual schedule of cuts to maintain the elevation of the bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced, with different frequencies, by a robot which can service only one machine at a time. The objective is to design a perpetual schedule of servicing which minimizes the maximum (weighted) waiting time for servicing. We consider two variants of BGT. In discrete BGT the robot trims only one bamboo at the end of each day. In continuous BGT the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next. For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel Scheduling Problem, we derive a 2-approximation for the general case and a tighter approximation when the growth rates are balanced. For continuous BGT, we propose approximation algorithms which achieve approximation ratios O(log(h_1/h_n)) and O(log n).

Bio: Ralf Klasing received the PhD degree from the University of Paderborn in 1995. From 1995 to 1997, he was an Assistant Professor at the University of Kiel. From 1997 to 1998, he was a Research Fellow at the University of Warwick. From 1998 to 2000, he was an Assistant Professor at RWTH Aachen. From 2000 to 2002, he was a Lecturer at King’s College London. In 2002, he joined the CNRS as a permanent researcher. From 2002 to 2005, he was affiliated to the laboratory I3S in Sophia Antipolis. Currently, he is affiliated to the laboratory LaBRI in Bordeaux. In 2009, he received the HDR degree from the University Bordeaux 1. In 2010, he was promoted to Senior Researcher (DR CNRS). From 2010 to 2015, he was the Head of the Combinatorics and Algorithms team of the LaBRI.
His research interests are in "Design and Analysis of Algorithms" and in "Complexity". More particularly, his research focuses on (1) Distributed algorithms, (2) Approximation algorithms for combinatorially hard problems, (3) Algorithmic methods for telecommunication, (4) Communication algorithms in networks. He has co-authored three book chapters, two Springer Monographs, and has published 53 papers in refereed international journals and 54 papers in refereed international conferences with proceedings. He has published 6 invited papers in international conferences. He has given 13 invited talks at international conferences, and 1 invited lecture series. He has edited 4 LNCS volumes, and 3 special issues of the international journals ACM Journal of Experimental Algorithmics, Journal of Computer and System Sciences, and Journal of Information Science and Engineering.

He is Managing Editor of the international journal Journal of Interconnection Networks. He is a member of the Editorial Board of the 10 international journals International Journal of Computer Mathematics: Computer Systems Theory, Journal of Parallel and Distributed Computing, Journal of Computer and System Sciences, Theoretical Computer Science, Discrete Applied Mathematics, Networks, Wireless Networks, Parallel Processing Letters, Fundamenta Informaticae, and Computing and Informatics. He is a member of the Steering Committee of IWOCA. He was a member of the Steering Committee of SIROCCO. He was the Conference Co-Chair of I-SPAN 2018, and the Chair of the Program Commmittees of BWIC 2011, SEA 2012, and ALGOSENSORS 2016 (Track on Distributed and Mobile Networks). He acted as the Co-Chair of the Program Committees of SSS 2013 (Track on Ad-hoc, Sensors, Mobile Agents and Robot Networks), FCT 2017, I-SPAN 2017, IWOCA 2020, ALGOSENSORS 2021, and as the Chair of the best paper award committee of CIAC 2017. He has acted as a member of the Program Committees of 48 wellacknowledged international conferences, including ICALP, STACS, MFCS, FCT, ISAAC, IWOCA, WAOA, OPODIS, SIROCCO and SOFSEM.