PROGRAM

Friday, October 22, 2021

                 Saturday, October 23, 2021

                 Sunday, October 24, 2021

 
Tutorial

• Evanthia Papadopoulou (University of Lugano, Switzerland)

Voronoi and Voronoi-like Diagrams, 16:00 – 17:00, October 22 (Chair: Chung-Shou Liao)

Abstract: Voronoi diagrams are versatile geometric partitioning structures that find diverse applications in Science and Engineering. Given a set of n simple geometric objects, called sites, their Voronoi diagram subdivides the surrounding space into regions of influence exerted by the given sites. These sites are often considered to be points, however, non-points such as line segments, circles, polygons, or polyhedra often model various realistic scenarios. Abstract Voronoi diagrams (AVDs) offer a unifying framework for many such constructs in the plane. In this talk, I will first survey fundamental differences between Voronoi diagrams of points and their counterparts of segments, circles, or AVDs. Because of these differences, some surprising open problems may still remain. For example, although linear-time algorithms for site-deletion in planar point Voronoi diagrams had been well-known to exist since the late 80’s, until recently no corresponding algorithms existed for non-point diagrams. Towards bridging such gaps, I will introduce abstract Voronoi-like diagrams, a relaxed Voronoi structure, whose flexibility can help design simple, yet efficient algorithms. A Voronoi-like diagram is a graph on the arrangement of the underlying bisector system whose (non-leaf) vertices are locally Voronoi, i.e., they are vertices in a Voronoi diagram of three sites. Using Voronoi-like graphs we can devise simple randomized incremental constructions under the general AVD framework. I will show this technique and also its analysis, which introduces a simple alternative to the standard backwards analysis, applicable to order-dependent structures. We envision that Voronoi-like graphs will turn out useful in various generalized scenarios, including Voronoi diagrams with disconnected regions and Voronoi diagrams in 3D.

 
Keynote Speeches

• Kazuo Iwama (RIMS, Kyoto University)

Bounded Hanoi, 09:00 – 10:00, October 23 (Chair: D. T. Lee )

Abstract: The classic Tower of Hanoi puzzle involves moving a set of disks on three pegs. The number of moves required for a given number of disks is easy to determine, but when the number of pegs is increased to four or more this becomes more challenging. After 75 years the answer for four pegs was resolved only recently, and this \emph{time complexity} question remains open for five or more pegs. In this article the\emph{space complexity}, i.e., how many disks need to be accommodated on the pegs involved in the transfer, is considered for the first time. Suppose $m$ disks are to be transferred from some peg $L$ to another peg $R$ using $k$ intermediate \emph{work pegs} of sizes $j_1,\ldots,j_k$, then how large can $m$ be? We denote this value by $H(j_1,\ldots,j_k)$. If $k=1$, as in the classic problem, the answer is easy: $H(j)=j+1$. We have the exact value for two work pegs, but so far only very partial results for three or more pegs. For example, $H(10!,10!)=26336386137601$ and $H(0!,1!,2!,…,10!)=16304749471397$, but we still do not know the value for $H(1,i,j)$ except for very small $i$ and $j$. This is a joint work with Mike Paterson, University of Warwick and will appear in AMM.

• Luca Trevisan (Bocconi University, Italy)

Broadcast and Epidemics on Random Networks, 16:00 – 17:00, October 23 (Chair: Kai-Min Chung)

Abstract: We discuss two processes on random networks.

First we discuss the flooding process, in which information is broadcast in a network in such a way that every informed node immediately informs all the neighbors. In dynamic networks in which nodes continually enter and exit the network, activating and deactivating random network links, we present a result showing that the process quickly converges to a state in which almost all nodes, or even all nodes, are informed, depending on whether or not dropped connections are replaced by new connections.

Then we discuss the SIR process of epidemic spreading applied to a model of random networks similar to the Watts-Strogatz model, in which there is a mix of “local” connections and “random long distance” connections. We establish thresholds for the value of R0 that leads to large-scale epidemic spreading and show that even this very simple model is able to recover a number of realistic features, such as the way the epidemic spreads via a series of local outbreaks, and how even a small number of “super-spreader” events can have a disproportionate impact.

We present these two results together to emphasize how they both reduce to similar questions (how large are the connected components of certain random graphs) that can be addressed with similar techniques (analyze a BFS-like exploration of the graph, delaying decisions about random edges as much as possible).

(Based on joint papers with L. Becchetti, A. Clementi, R. Denni, F. Pasquale, I. Ziccardi)

• Prudence Wong (University of Liverpool, UK)

Scheduling to Optimize Energy and Electricity Cost,16:00 17:00, October 24 (Chair: Siu-Wing Cheng)

Abstract: Energy usage is a big concern these days in terms of computation and household usage. This motivates the revisit of classical scheduling problems to take energy into concern. In this talk, we will give an overview of several scheduling problems that attempt to optimize energy and electricity cost. In terms of processor scheduling, we investigate how to use speed scaling and sleep management to reduce energy usage effectively while providing certain level of quality of service. We also investigate how multi-processor scheduling can help reducing energy usage. In terms of household usage, we investigate the so called demand response management in electricity grid. We will also explore the relations of electricity grid scheduling and classical machine scheduling.

 
Session A1 Online & Approximation Algorithms (Session Chair: Chung-Shou Liao)

• 10:20-10:40 Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen and Kazuo Iwama. Tight Competitive Analyses of Online Car-sharing Problems
• 10:40-11:00 Hao-Ping Yeh, Wei Lu, Li-Hsuan Chen, Ling-Ju Hung, Ralf Klasing and Sun-Yuan Hsieh. Approximation Algorithms for the Star p-Hub Center Routing Problem
• 11:00-11:20 Shi-Chun Tsai, Meng-Tsung Tsai and Tsung-Ta Wu. An Empirical Study of Finding a Most Frequent Fraction and Its Applications
• 11:20-11:40 Yi-Chang Liang and Hung-Lung Wang. The colorful knapsack center problem
• 11:40-12:00 Sheng-Yen Ko, Ho-Lin Chen, Siu-Wing Cheng, Wing-Kai Hon and Chung-Shou Liao. General Max-Min Fair Allocation

Session B1 Geometric Computing (Session Chair: Hee-Kap Ahn)

• 10:20-10:40 Andrew Bloch-Hansen, Roberto Solis-Oba and Andy Yu. High Multiplicity Strip Packing with Three Rectangle Types
• 10:40-11:00 Siu-Wing Cheng and Man Ting Wong. Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions
• 11:00-11:20 Hwi Kim, Jaegun Lee and Hee-Kap Ahn. Rectangular Partitions of a Rectilinear Polygon
• 11:20-11:40 Jongmin Choi, Dahye Jeong and Hee-Kap Ahn. Covering Convex Polygons by Two Congruent Disks
• 11:40-12:00 Mincheol Kim and Hee-Kap Ahn. Minimum-Link Shortest Paths for Polygons amidst Rectilinear Obstacles

Session A2 Miscellaneous Topics (Session Chair: Po-An Chen)

• 14:00-14:20 Ching-Hsiang Lin and Wing-Kai Hon. Duality Theorem in Kontsevich’s Pebble Game and Its Generalization
• 14:20-14:40 Po-An Chen, Yiling Chen, Chi-Jen Lu and Chuang-Chieh Lin. Profitable Prediction Market Making
• 14:40-15:00 Yu-Lun Wu and Hung-Lung Wang. Correcting matrix products over the ring of integers
• 15:00-15:20 Kaito Suzuki, Diptarama Hendrian, Ryo Yoshinaka and Ayumi Shinohara. Query Learning of Symbolic Weighted Finite Automata
• 15:20-15:40 Yu-Hsuan Huang, Yao-Ching Hsieh and Mi-Ying Huang. Accountable Ring Signature From Isogeny Group Action

Session B2 Online & Approximation Algorithms (Session Chair: Hyung-Chan An)

• 14:00-14:20 Yongho Shin and Hyung-Chan An. Making Three Out of Two: Three-Way Online Correlated Selection
• 14:20-14:40 Taehoon Ahn, Jongmin Choi, Chaeyoon Chung, Hee-Kap Ahn, Sang Won Bae and Sang Duk Yoon. Rearranging a Sequence of Points onto a Line
• 14:40-15:00 Byeonguk Kang, Jongmin Choi and Hee-Kap Ahn. Intersecting Disks using Two Congruent Disks
• 15:00-15:20 Fu-Hong Liu, Hsiang-Hsuan Liu and Prudence W.H. Wong. Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs
• 15:20-15:40 Jonathan Toole-Charignon and Hsiang-Hsuan Liu. Online Independent Set with Amortized Late Accept/Reject

Session A3 Graph Theory & Graph Algorithms (Session Chair: Wing-Kai Hon)

• 14:00-14:20 Hsiao-Yu Hu, Ya-Chun Liang, Jian-Xi Shao and Chung-Shou Liao. Learning-Augmented Algorithms for Online TSP
• 14:20-14:40 Cheng-Hung Chiang and Meng-Tsung Tsai. Single-Pass Streaming Algorithms to Partition Graphs into Few Forests
• 14:40-15:00 Chun-Hsiang Chan, Cheng-Yu Shih and Ho-Lin Chen. On the Computational Power of Phosphate Transfer Reaction Networks
• 15:00-15:20 Dun-Wei Cheng, Jo-Yi Chang, Chen-Yen Lin, Limei Lin, Yanze Huang, Krishnaiyan Thulasiraman and Sun-Yuan Hsieh. Node Failure Survivability: An Efficient Logical Topology Mapping Algorithm for IP-over-WDM Optical Networks
• 15:20-15:40 Dun-Wei Cheng, Kai-Hsun Yao and Sun-Yuan Hsieh. The Construction of Multiple Independent Spanning Trees on Generalized Recursive Circulant Graphs

Session B3 Miscellaneous Topics (Session Chair: Hirotaka Ono)

• 14:00-14:20 Hiroshi Eto, Hironori Kiya and Hirotaka Ono. Hardness Results on Generalized Puyopuyo
• 14:20-14:40 Taekang Eom, Seungjun Lee and Hee-Kap Ahn. Largest similar copies of convex polygons in polygon
• 14:40-15:00 Corentin Allair and Antoine Vigneron. Pattern Matching in Doubling Spaces
• 15:00-15:20 Jihoon Hyun, Sewon Park and Martin Ziegler. Lazy Data Types
• 15:20-15:40 Koya Watanabe, Diptarama Hendrian, Ryo Yoshinaka, Takashi Horiyama and Ayumi Shinohara. Efficient Construction of Cryptarithm Catalogues over Deterministic Finite Automata